1.2 递归与递推
1. 递推与递归的宏观描述
- 对于一个待求解的问题，我们由已知的某个小问题进而一步一步推向该问题的方法称为递推
- 递归正好与递推的方向相反，它是由大问题逐步分解为小问题，然后回溯到大问题进行解决的方法。
2. 递推与递归的简单应用
| 枚举形式 | 状态空间规模 | 一般遍历方式 |
| 多项式 | nk,k为常数 | 循环、递推 |
| 指数 | kn,k为常数 | 递归、位运算 |
| 排列 | n！ | 递归、C++ next_permutation |
| 组合 | $inom{n}{m}$ | 递归+剪枝 |
3. 分治
把一个问题分解成若干个规模更小的同类子问题，对这些子问题求解，然后在回溯时通过他们推导出原问题的解。
4. 递归的机器实现
可以通过维护一个栈，将调用函数和返回函数的压栈出栈过程进行模拟，从而将递归实现循环。
相关练习：
1. 0301 递归实现指数型枚举
#include<iostream>
#include<vector>
using namespace std;
vector<int> ans;
int n, flag;
void dfs(int dep, int idx){
if(dep == 0){
for(auto i : ans)
cout<<i <<' ';
cout<<endl;
return ;
}
for(int i = idx; i <= n; ++i){
if(!(flag & (1 << i))){
flag += 1 << i;
ans.push_back(i);
dfs(dep-1, i+1);
ans.pop_back();
flag -= 1 << i;
//dfs(dep, i);
}
}
}
int main(){
cin>>n;
for(int i = 0; i <= n; ++i)
dfs(i, 1);
return 0;
}
2. 0302 递归／非递归实现组合型枚举
//递归型
#include<iostream>
#include<vector>
using namespace std;
vector<int> ans;
int n, m;
void dfs(int x){
if(ans.size() == m){
for(auto i: ans)
cout<<i<<' ';
cout<<endl;
return ;
}
for(int i = x; i <= n; ++i){
ans.push_back(i);
dfs(i+1);
ans.pop_back();
}
}
int main(){
cin>>n>>m;
dfs(1);
return 0;
}
//递推型
#include<iostream>
#include<deque>
using namespace std;
struct info{
char x;
deque<char> t;
};
int n, m;
deque<info> st;
int main(){
cin>>n>>m;
st.push_back({1, {}});
while(st.size()){
auto t = st.front();
st.pop_front();
if(n - t.x + 1 < m - t.t.size()) continue;
for(int k = t.x; k <= n; ++k){
info l = t;
if(t.t.size() < m){
l.t.push_back(k);
l.x = k + 1;
st.push_back(l);
}
}
if(t.t.size() == m){
for(auto x: t.t)
printf("%d ", x);
cout<<endl;
}
}
return 0;
}
3. 0303 递归实现排列型枚举
#include<iostream>
#include<vector>
using namespace std;
vector<int> ans;
int n, flag;
void dfs(int x){
if(x > n){
for(auto i: ans)
cout<<i<<' ';
cout<<endl;
return;
}
for(int i = 1; i <= n; ++i ){
if(!(flag & (1 << i))){
ans.push_back(i);
flag += 1 << i;
dfs(x + 1);
ans.pop_back();
flag -= 1 << i;
}
}
}
int main(){
cin>>n;
dfs(1);
return 0;
}
4. 0201 费解的开关
#include<iostream>
#include<vector>
using namespace std;
//#define _Debug
int n;
vector<string> record;
const int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
void change(int x, int y, vector<string>& s){
char & t = s[x][y];
if(t == '1') t = '0';
else t = '1';
}
void set_bit(int x, int y, vector<string>& t){
change(x, y, t);
for(int i = 0; i < 4; ++i){
int nx = x + dx[i], ny = y + dy[i];
if(nx >= 0 && ny >= 0 && nx < 5 && ny < 5){
change(nx, ny, t);
}
}
}
int get_res(){
int minv = 0x3f3f3f3f;
for(int i = 0; i < (1 << 5) -1; ++i){
vector<string> t = record;
#ifdef _Debug
cout<<i<<endl;
cout<<t[1]<<endl;
#endif
int step = 0;
for(int j = 0; j < 5; ++j){
if(i & (1 << j)){
++step;
set_bit(0, j, t);
}
}
#ifdef _Debug
cout<<t[1]<<endl;
#endif
for(int j = 0; j < 4; ++j){
for(int k = 0; k < 5; ++k)
if(t[j][k] == '0')
set_bit(j+1, k, t), ++step;
}
bool flag = true;
for(int i = 0; i < 5; ++i){
if(t[4][i] == '0') flag = false;
}
if(flag) minv = min(minv, step);
}
return minv;
}
int main(){
cin>>n;
while(n --){
string t;
for(int i = 0; i < 5; ++i){
cin>>t;
record.push_back(t);
}
int step = get_res();
if(step <= 6) cout<<step<<endl;
else puts("-1");
record.clear();
}
return 0;
}
5. POJ1958 Strange Towers of Hanoi
#include<iostream>
#include<cstring>
using namespace std;
const int N = 20;
int dp3[N], dp4[N];
int main(){
memset(dp3, 0x3f, sizeof dp3), memset(dp4, 0x3f, sizeof dp4);
dp3[0] = 0, dp4[0] = 0;
for(int i = 1; i < 13; ++i) dp3[i] = dp3[i - 1] * 2 + 1;
for(int i = 1; i < 13; ++i)
for(int j = 0; j <= i; ++j)
dp4[i] = min(dp4[i], dp4[j] * 2 + dp3[i - j]);
for(int i = 1; i < 13; ++i)
cout<<dp4[i]<<endl;
return 0;
}