递归与递推1-7

递推的一种形式就是动态规划，则不停的由小问题去解决大问题：

经典的动态规划问题，那么这道题怎么来解呢？我想初学者根据做题的经验，可能会说用深搜算法，也就是dfs，?首先这个方法在逻辑上是没有任何问题的，但是在时间复杂度上面就有大大的问题了，下面见深搜算法

#include 
    using namespace std; int ans=0; int n; void dfs(int k) //递归算法 ，k表示当前走的楼梯数量 { 
    if(k>n) //终止条件，当走的楼梯数量大于已有的楼梯数量，返回 return ; if(k==n) //终止条件，当走的楼梯数量等于已有的楼梯数量，答案+1，返回 { 
    ans+=1; return; } dfs(k+1); //要么一次走一阶楼梯 dfs(k+2);//要么一次走两阶楼梯 } int main() { 
    cin>>n; dfs(0); cout<<ans; return 0; } 

#include 
    #include 
    using namespace std; long long int f[1000]; int main() { 
    int n; cin>>n; f[1]=1; f[2]=2; for(int i=3;i<=n;i++) f[i]=f[i-1]+f[i-2]; cout<<f[n]; return 0; } 

这个代码就是递推的核心了，但是考虑到n的数字很大，即使是long long也不够，那么要用到高精度。（不知道高精度的我之前的博客有介绍），知道的这道题自己尝试完成，下面代码写的不好（但是是满分的)不建议看。但是最重要的思想已经介绍了。好了下一题。

 #include 
    using namespace std; int n; int a[10000]; int b[10000]; int a_len = 1; int b_len = 1; void add(int* a, int* b,int k) { 
    int c[10000]; int max = (a_len >= b_len) ? a_len : b_len; int min = (a_len >= b_len) ? b_len : a_len; int i = 1; int j = 1; int jinwei = 0; for (i; i <= max; i++) { 
    int temp = (a[i] + b[i] + jinwei) / 10; c[i] = (a[i] + b[i] + jinwei) % 10; jinwei = temp; } while (jinwei > 0) { 
    c[i++] = jinwei % 10; jinwei /= 10; } if (k ==1) { 
    for (int j =1; j<i; j++) { 
    a[j] = c[j]; } a_len = i - 1; } else //k==1 { 
    for (int j = 1; j < i; j++) { 
    b[j] = c[j]; } b_len = i - 1; } } void Dynamic() { 
    a[1] = 1; b[1] = 2; for (int i=1;i<=n-2;i++) { 
    if (i % 2 == 1) add(a, b,1); else if (i % 2 == 0) add(a, b,0); } } int main() { 
    cin >> n; if (n == 1) { 
    printf("1"); return 0; } Dynamic(); if ((n - 2) % 2 == 1) { 
    for (int i = a_len; i >= 1; i--) printf("%d", a[i]); } else { 
    for (int i = b_len; i >= 1; i--) printf("%d", b[i]); } return 0; } 

这道题要分开来看，一步步来，首先不看马在什么位置，先解决这样一个问题，从A到B有几种行走方案？
细心的道友会发现，这是不是和上面那个爬楼梯有点相似？上面的楼梯要么一次走两格，要么一次走一格，这里的卒要么向下走一格，要么向右走一格。。。。。想一想，发现。当卒在（i，j）(i行j列）位置的时候，他要么是从（i-1，j）走过来的，要么是从（i，j-1）走过来的。咦？那是不是可以说这个递推式就写出来了呢？ ? f[i][j]=f[i-1][j]+f[i][j-1] ? 翻译一下就是：卒走到(i,j)的行走方案个数=卒走到(i-1,j)的行走方案个数+卒走到(i,j-1)的行走方案个数

#include 
    #include 
    using namespace std; #define ll long long ll f[1000][1000]; //f[i][j]代表走到位置[i][j]的方案个数 int main() { 
    int horse_x,horse_y,terminal_x,terminal_y; cin>>terminal_x>>terminal_y>>horse_x>>horse_y; f[0][1]=1; f[1][0]=1; for(int i=1;i<=terminal_x;i++) for(int j=1;i<=terminal_y;j++) { 
    f[i][j]=f[i-1][j]+f[i][j-1]; } cout<<f[terminal_x][terminal_y]; return 0; } 

上面的代码就是从源点(0,0)走到终点(terminal_x.terminal_y)的所有方案，是不考虑马的。那么现在考虑马了。(献上满分代码)

#include 
    #include 
    using namespace std; #define ll long long ll f[1000][1000]; //f[i][j]代表走到位置[i][j]的方案个数 int map[1000][1000]; int main() { 
    int horse_x, horse_y, terminal_x, terminal_y; cin >> terminal_x >> terminal_y >> horse_x >> horse_y; //由于马周围8个点都不能走，所以将这8个点都标记下来 //由于数组下标不能是负数，所以要预处理一下. horse_x += 2; //都加上2，相对坐标不变，而且满足了horse-2>0 horse_y += 2; terminal_x += 2; terminal_y += 2; map[horse_x][horse_y] = map[horse_x - 1][horse_y - 2] = map[horse_x + 1][horse_y - 2] = map[horse_x - 2][horse_y - 1] = map[horse_x - 2][horse_y + 1] = 1; map[horse_x - 1][horse_y + 2] = map[horse_x + 1][horse_y + 2] = map[horse_x + 2][horse_y + 1] = map[horse_x + 2][horse_y - 1] = 1; //注意，因为相对坐标加（2，2），所以原点坐标也变了，也是（2，2） f[2][3] = 1; f[3][2] = 1; for (int i = 2; i <= terminal_x; i++) { 
    for (int j = 2; j <= terminal_y; j++) { 
    if (map[i][j] == 1) { 
    f[i][j] = 0; } else if(f[i][j]==0) //这一步的目的是因为：f[2][3]=1.这个最开始的值不能被覆盖了。后面的数要从这个基础加上去 { 
    f[i][j] = f[i - 1][j] + f[i][j - 1]; } } } cout << f[terminal_x][terminal_y]; return 0; } 

#include 
    using namespace std; #define ll long long  ll f[1000][1000]; int main() { 
    int n; cin >> n; f[1][0] = 1; for (int i = 1; i <= n; i++) f[0][i] = 1; for (int i = 1; i <= n; i++) //i表示队里元素个数 { 
    for (int j = 0; j <= n - i; j++) //j表示栈里元素个数 { 
    if (j - 1 >= 0) f[i][j] = f[i][j - 1] + f[i - 1][j + 1]; else f[i][j] = f[i - 1][j + 1]; } } cout << f[n][0]; return 0; } 

那么有道友会问，能不能用递归来写？答案是可以的。因为上面已经分析了，对于任意一个状态f[i][j];

• f[i][j]=f[i][j-1]+f[i-1][j+1](把这两个分解式继续拆）

1. f[i][j-1]=f[i][j-1-1]+f[i-1][j-1+1]
2. f[i-1][j+1]=f[i-1][j+1-1]+f[i-1-1][j+1+1]
   这样无限拆分直到i=0，而f[0][j]=1.
   
   

#include 
    using namespace std; #define ll long long  ll f[1000][1000]; ll dfs(int i,int j) //记忆化搜索加深搜 { 
    if(i==0) //i==0代表队列里没有元素了，那么只能出栈得到一个方案 return 1; if(f[i][j]!=0) //记忆化搜索的精髓，如果当前状态不是0，则说明当前状态已经被计算过，那么直接返回当前值 return f[i][j]; if(j-1>=0) //栈里有元素就可以出栈 f[i][j]+=dfs(i,j-1); f[i][j]+=dfs(i-1,j+1); //然后出队 return f[i][j]; //最后把这两种方法的方案之和返回，就是最终答案 } int main() { 
    int n; cin>>n; dfs(n,0); return 0; } 

1. f[1]: 1, (1种）
2. f[2]: 2,12,(2种）
3. f[3]: 3,13,(2种）
4. f[4]: 4,14,24,124,(4种）
5. f[5]:5,15,25,125,(4种）
6. f[6]:6,16,26,126,36,136,(6种）
7. f[7]:7,17,27,127,37,137,(6种）
8. f[8]:8,18,28,128,38,138,48,248,1248,(9种）
9. f[9]:9,19,29,129,39,139,49,249,1249,(9种）
   10.f[10]:10,110,210,1210,310,1310,410,2410,12410,510,1510,2510,12510, (13种）
   
   

#include 
    using namespace std; #define ll long long  ll f[1000]; int main() { 
    int n; cin>>n; f[1]=1; f[2]=2; f[3]=2; for(int i=2;i<=n;i++) { 
    if(i%2==0) { 
    f[i]=f[i-1]+f[i/2]; } else { 
    f[i]=f[i-1]; } } cout<<f[n]; return 0; } 

算8的组合

算16的组合

#include 
   //万能头文件 using namespace std; int n; int f[1001];//存每一位数的种类 int main(){ 
    cin>>n; for(int i=1;i<=n;i++){ 
    //1-n的递推 for(int j=1;j<=i/2;j++){ 
    f[i]+=f[j]; //每一位叠加，递推走起 } f[i]++; //加上本身 } cout<<f[n];//输出n的种类 return 0; } 

这道题已经在最下面提示了，记忆化搜索，那么就根据题意来写就好了

#include 
    using namespace std; #include 
    #pragma warning (disable:4996) long long int f[25][25][25]; //记忆化搜索的辅助数组 long long int dfs(long long int a,long long int b,long long int c) { 
    if (a <= 0 || b <= 0 || c <= 0) { 
    return 1; } else if (f[a][b][c]!=0) return f[a][b][c]; else if (a > 20 || b > 20 || c > 20) { 
    f[a][b][c] = dfs(20, 20, 20); return f[a][b][c]; } else if (a < b && b < c) { 
    f[a][b][c] = dfs(a, b, c - 1) + dfs(a, b - 1, c - 1) - dfs(a, b - 1, c); return f[a][b][c]; } else { 
    f[a][b][c] = dfs(a - 1, b, c) + dfs(a - 1, b - 1, c) + dfs(a - 1, b, c - 1) - dfs(a - 1, b - 1, c - 1); return f[a][b][c]; } } int main() { 
    long long int a, b, c; while (scanf("%lld%lld%lld", &a, &b, &c) == 3) { 
    if (a == -1 && b == -1 && c == -1) break; printf("w(%lld, %lld, %lld) = ", a, b, c); if (a > 20) a = 21; if (b > 20) b = 21; if (c > 20) c = 21; printf("%lld\n",dfs(a, b, c)); } return 0; } 

#include 
    #include 
    #include 
    #pragma warning (disable:4996) using namespace std; string jieya() { 
    int k; //解压次数 char ch; string s = "", str = ""; while (cin >> ch) { 
    if (ch == '[') //如果遇到左括号，继续递归 { 
    cin >> k; str = jieya(); //这里会一直递过去，最后归一个最里层的字符串 while (k > 0) //然后将这个字符串赋值k次 { 
    s += str; k -= 1; } } else if (ch == ']') //这是递归返回的终止条件，说明不需要继续递归下去了，把当前的字符串返回 { 
    return s; } else s += ch; } } int main() { 
    cout << jieya(); return 0; } 

#include 
    #include 
    using namespace std; int n, m; int a[10000]; int b[10000]; int a_len = 1; int b_len = 1; void add(int* a, int* b,int k) { 
    int temp[10000]; int max = (a_len >= b_len) ? a_len : b_len; int jinwei = 0; int i; for (i = 0; i < max; i++) { 
    temp[i] = (a[i] + b[i] + jinwei) % 10; jinwei = (a[i] + b[i] + jinwei) / 10; } while (jinwei > 0) { 
    temp[i++] = jinwei % 10; jinwei /= 10; } if (k == 1) //将temp的值给a { 
    a_len = i; i--; while (i >=0) { 
    a[i] = temp[i]; i--; } } else { 
    b_len = i; i--; while (i >=0) { 
    b[i] = temp[i]; i--; } } } int main() { 
    int n, m; cin >> n >> m; a[0] = 1; b[0] = 1; for (int i = n+2; i <= m; i++) //f[i]=f[i-1]+f[i-2] { 
    if (i % 2 == 0) add(a, b,1); //a+b的结果覆盖原来的a else add(a, b,0); //a+b的结果覆盖原来的b } if (m % 2 == 0) { 
    for (int i = a_len-1; i>=0; i--) cout << a[i]; } else { 
    for (int i = b_len-1; i>=0; i--) cout << b[i]; } return 0; }