11.1 动态规划的递归写法与递推写法

11.1.1 什么是动态规划

11.1.2 动态规划的递归写法（斐波那契）

  1. #include <cstdio>
  2. #include <string.h>
  3. const int maxn = 10010;
  4. int dp[maxn];
  5. int F(int n)
  6. {
  7.     if(n == 0 || n == 1)
  8.     {
  9.         return 1;
  10.     }
  11.     if(dp[n] != -1)
  12.     {
  13.         return dp[n];
  14.     }
  15.     else{
  16.         dp[n] = F(n-2) + F(n-1);
  17.         return dp[n];
  18.     }
  19. }
  20. int main()
  21. {
  22.     memset(dp, -1, sizeof (dp));
  23.     int r = F(5);
  24.     printf("%d\n",r);
  25.     return 0;
  26. }

如果使用大一学的普通的递归，那复杂度就是O(2**n**)， 对于稍微大一些的工作量就无法承担。因此，使用记忆化搜索显得尤为重要，不需要不断地重复计算，可以将复杂度降到O(n)。
psps: 之前不能AC是因为赋初值的问题，int dp[maxn] = {-1}，只是将第一个数赋值为-1，其余仍为0，因此需要使用memset.

11.1.3 动态规划的递推写法（数塔问题）（P427）

动态规划的递推写法就是从边界出发，通过状态转移方程扩散到整个dp数组。
以数塔问题为例，最后一层的dp就是f的值，然后依次一层一层利用状态转移方程往上推，最后dp[1][1]的值即为最终解。

  1. #include <cstdio>
  2. #include <algorithm>
  3. using namespace std;
  4. const int maxn = 10010;
  5. int f[maxn][maxn], dp[maxn][maxn];
  6. int main()
  7. {
  8.     int n,k;
  9.     scanf("%d",&n);
  10.     for(int i = 1; i <= n; ++i)
  11.     {
  12.         for(int j = 1; j <= i; ++j)
  13.         {
  14.             scanf("%d",&f[i][j]);
  15.         }
  16.     }
  17.     // 设置边界，最后一层dp值即为f值
  18.     for(int j = 1; j <= n; ++j)
  19.     {
  20.         dp[n][j] = f[n][j];
  21.     }
  22.     for(int i = n-1; i >= 1; --i)
  23.     {
  24.         for(int j = 1; j <= i; ++j)
  25.         {
  26.             dp[i][j] = max(dp[i + 1][j], dp[i + 1][j + 1]) + f[i][j];
  27.         }
  28.     }
  29.     printf("%d\n",dp[1][1]);
  30.     return 0;
  31. }

11.2 最大连续子序列和

  1. // P430  最大连续子序列和
  2. #include <cstdio>
  3. #include <algorithm>
  4. using namespace std;
  5. const int maxn = 10010;
  6. int A[maxn], dp[maxn];  // A[i]存放序列，dp[i]存放以A[i]结尾的连续序列的最大和
  7. int main()
  8. {
  9.     int n;
  10.     scanf("%d",&n);
  11.     for(int i = 0; i < n; ++i){
  12.         scanf("%d",&A[i]);
  13.     }
  14.     // 边界
  15.     dp[0] = A[0];
  16.     // dp[0]已赋值，下面从1~n-1赋值
  17.     for(int i = 1; i < n; ++i)
  18.     {
  19.         // 状态转移方程
  20.         dp[i] = max(A[i], dp[i - 1] + A[i]);
  21.     }
  22.     // dp[i]存放以A[i]结尾的连续序列的最大和，需要遍历i得到最大的才是结果
  23.     int k = 0;
  24.     for(int i = 1; i < n; ++i)
  25.     {
  26.         if(dp[i] > dp[k])
  27.         {
  28.             k = i;
  29.         }
  30.     }
  31.     printf("%d\n",dp[k]);
  32.     return 0;
  33. }

11.3 最长不下降子序列（LIS）

  1. #include <cstdio>
  2. #include <algorithm>
  3. using namespace std;
  4. const int maxn = 10010;
  5. int A[maxn], dp[maxn];
  6. int main()
  7. {
  8.     int n;
  9.     scanf("%d",&n);
  10.     for(int i = 1; i <= n; ++i)
  11.     {
  12.         scanf("%d",&A[i]);
  13.     }
  14.     int ans = -1;
  15.     for(int i = 1; i <= n; ++i) // 按顺序计算出dp[i]的值
  16.     {
  17.         dp[i] = 1;   // 边界初始条件
  18.         // 接上，因为dp[i]要么就是A[i]自己，要么就是某下标j,dp[j]+1
  19.         for(int j = 1; j < i; ++j)
  20.         {
  21.             if(A[j] <= A[i] && dp[j] + 1 > dp[i])
  22.             {
  23.                 // 状态转移方程，用以更新dp[i]
  24.                 dp[i] = dp[j] + 1;
  25.             }
  26.         }
  27.         ans = max(dp[i], 1);
  28.     }
  29.     printf("%d\n",ans);
  30.     return 0;
  31. }

动态规划问题的核心就是涉及状态转移方程，以及边界问题。此问题类似于最大连续子序列之和的问题，分别遍历1~n，把A[i}作为结尾元素分别更新dp[i].

11.4 最长公共子序列

题解：

此题的核心是设计状态转移函数和边界。
image.png

  1. // P434 最长公共子序列（LCS）
  2. #include <cstdio>
  3. #include <algorithm>
  4. #include <cstring>
  5. using namespace std;
  6. const int maxn = 10010;
  7. char A[maxn], B[maxn];
  8. int dp[maxn][maxn];
  9. int main()
  10. {
  11. //    int n;
  12.     gets(A + 1);
  13.     gets(B + 1);
  14.     int lenA = strlen(A + 1);
  15.     int lenB = strlen(B + 1);
  16.     for(int i = 1; i <= lenA; ++i)
  17.     {
  18.         dp[i][0] = 0;
  19.     }
  20.     for(int j = 1; j <= lenB; ++j)
  21.     {
  22.         dp[0][j] = 0;
  23.     }
  24.     for(int i = 1; i <= lenA; ++i)
  25.     {
  26.         for(int j = 1; j <= lenB; ++j)
  27.         {
  28.             if(A[i] == B[j])
  29.                 dp[i][j] = dp[i - 1][j - 1] + 1;
  30.             else
  31.                 dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
  32.         }
  33.     }
  34.     printf("%d", dp[lenA][lenB]);
  35.     return 0;
  36. }