动态规划（Dynamic Programming）

一、动态规划相关的知识

• 动态规划是一种思想，它没有固定的写法、及其灵活，常常需要具体问题具体分析。
• 动态规划是一种用来解决一类最优化问题的算法思想。动态规划将一个复杂的问题分解成若干个子问题，通过综合子问题的最优解来得到原问题的最优解。需要注意的是，动态规划会将每个求解过的子问题的解记录下来，这样当下次碰到同样的子问题时，就可以直接使用之前记录的结果，而不是重复计算。
• 重叠子问题：如果一个问题可以被分解为若干个子问题，且这些子问题会重复出现，那么称这个问题拥有重叠子问题（overlapping subproblems）。动态规划通过记录重叠子问题的解，来使下次碰到相同的子问题时直接使用之前记录的结果，以此避免大量重复计算。因此，一个问题必须拥有重叠子问题，才能使用动态规划去解决。
• 最优子结构：如果一个问题的最优解可以由其子问题的最优解有效的构造出来，那么称这个问题拥有最优子结构（optimal substructure）。最优子结构保证了动态规划中原问题的最优解可以由子问题的最优解推导出来。因此，一个问题必须拥有最优子结构，才能使用动态规划去解决。
• 一个问题必须拥有重叠子问题和最优子结构，才能使用动态规划去解决。
• 分治与动态规划。
  • 分治和动态规划都是将问题分解为子问题，然后合并子问题的解得到原问题的解。
  • 不同的是，分治法分解出的子问题是不重叠的，因此分治法解决的问题不拥有重叠子问题，而动态规划解决的问题拥有重叠子问题。
  • 分治解决的问题不一定是最优化问题，而动态规划解决的问题一定是最优化问题。
• 贪心与动态规划。
  • 贪心和动态规划都要求原问题必须拥有最优子结构。
  • 贪心总是只在上一步选择的基础上继续选择，因此整个过程以一种单链的流水方式进行，显然这种所谓的 ”最优选择“ 的正确性需要用归纳法证明。
  • 动态规划总是会考虑所有子问题，并选择继承能得到最优结果的那个，对暂时没被选继承到的子问题，由于重叠子问题的存在后期可能会再次考虑它们，因此还有机会成为全局最优解的一部分，不需要放弃。
  • 贪心是一种壮士断腕的决策，只要进行了选择，就不后悔；而动态规划则要看哪个选择笑到了最后，暂时的领先说明不了什么。
• 一般使用递归或者递推的写法来实现动态规划，其中递归写法又称为记忆化搜索。
• 递推和递归的区别：使用递推写法的计算方式是自底向上（bottom-up approach），即从边界开始，不断向上解决问题，直到解决到目标问题；而使用递归写法的计算方式是自顶向下（top-down approach），即从目标问题开始，将它分解成子问题的组合，直到分解至边界为止。
• 状态的无后效性： 当前状态记录了历史信息，一旦当前状态确定，就不会再改变，且未来的决策只能在已有的一个或若干个状态的基础上进行，历史信息只能通过已有的状态去影响未来的决策。
• 对动态规划可解的问题来说，总会有很多设计状态的方式，但并不是所有的状态都具有无后效性，因此必须设计一个拥有无后效性的状态以及相应的状态转移方程，否则动态规划就没有办法得到正确结果。
• 如何设计状态和状态转移方程，才是动态规划的核心，而它们也是动态规划最难的地方。
• 多阶段动态规划问题：
  • 有一类动态规划可解的问题，它可以描述成若干个有序的阶段，且每个阶段的状态只和上一个阶段的状态有关，一般把这类问题称为多阶段动态规划问题。
  • 显然，对这种问题，只需要从第一个问题开始，按照阶段的顺序解决每个阶段中状态的计算，就可以得到最后一个阶段中的状态的解。

二、经典的动态规划模型

（1）数塔 dp

• 状态： 令 dp[i][j] 表示从第 i 行第 j 个数字出发的到达最底层的所有路径上所能得到的最大和。

• 状态转移方程：

  dp[i][j] = max(dp[i+1][j], dp[i+1][j+1]) + f[i][j];
  

• 边界： 数塔的最后一层的 dp 值总是等于元素本身。

• 结果： dp[1][1] 的值就是最后的结果。

（2）最大连续子序列和

• 状态： 令 dp[i] 表示以 a[i] 作为末尾的连续序列的最大和。

• 状态转移方程：

  dp[i] = max(a[i], dp[i-1]+a[i]);
  

• 边界： dp[0] = 0

• 结果： 要求的最大和其实就是 dp 数组中的最大值，因为到底以哪个元素结尾未知。

• 总结：

  • 求最大连续子序列和的时候其实可以不需要一个动态数组来进行专门的存储，只需要一个变量在寻找的过程中记录中间最大的结果就可以找出最大连续子序列。

（3）最大子矩阵之和

• 将二维的转化为一维的最大连续子序列和，进行行压缩。
• 枚举两列假设，然后将行看成是求一维的最大连续和的方式进行求解就好。
• 其实就有点相当于一行一行的加，直到找到最大的值为止啦。
• 这个问题进行暴力求解的时间复杂度为 o(n的六次方)
• 这个问题进行一维前缀和优化求解的时间复杂度为 o(n的五次方)
• 这个问题进行二维前缀和优化求解的时间复杂度为 o(n的四次方)
• 这个问题进行动态规划求解的时间复杂度为 o(n的3次方)

（4）最长不下降(上升)子序列（lis）

• 状态： 令 dp[i] 表示以 a[i] 结尾的最长不下降子序列的长度。
• 状态转移方程：

  dp[i] = max(1, dp[j] + 1); (j = 1,2,..,i-1 && a[j] <= a[i])
  

• 边界： dp[i] = 1
• 结果： 要求的最大长度其实就是 dp 数组中的最大值，因为到底以哪个元素结尾未知。

（5）最长公共子序列（lcs）

• 状态： 令 dp[i][j] 表示字符串 a 的 i 号位和字符串 b 的 j 号位之前的 lcs 长度（下标从 1 开始）。
• 状态转移方程：

  //如果 a[i] == b[i]
  dp[i][j] = dp[i-1][j-1] + 1;
  //如果 a[i] != b[i]
  dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
  

• 边界： dp[i][0] = dp[0][j] = 0 (0 <= i <= n, 0 <= j <= m)
• 结果： 最终 dp[n][m] 就是需要的答案。

（6）最长回文字符串

• 状态： 令 dp[i][j] 表示 s[i] 至 s[j] 所表示的字串是否是回文子串，是则为 1， 不是则为 0。

• 状态转移方程：

  //s[i] == s[j]
  dp[i][j] = dp[i+1][j-1];
  //s[i] != s[j]
  dp[i][j] = 0;
  
  //如果按照i 和 j 从小到大的顺序来枚举字串的两个端点，然后更新 dp[i][j]，会无法保证 dp[i+1][j-1] 已经被计算过，从而无法得到正确的 dp[i][j]。
  //事实上，无论对 i 和 j 的枚举顺序做何调整，都无法调和这个矛盾，因此必须想办法寻找新的枚举方式。
  //根据递推写法从边界出发的原理，注意到边界表示的是长度为 1 和 2 的字串，且每次转移时都对字串的长度减了 2 ，因此不妨考虑按字串的长度和字串的初始位置进行枚举。
  //最长回文字串问题，可以使用二分 + 字符串 hash 的做法，复杂度为 o(nlogn)，manacher算法的复杂度为 o(n)，动态规划的复杂度为 o(n的二次方)。
  

• 边界： dp i i = 1，dp i i+1 = (s[i] == s[i+1]) ? 1 : 0。

• 结果： 动态二维数组中元素为 1 的所在行数就是存在回文子字符串，所以行数最大的就是最大的回文子字符串。

（7）dag(有向无环图)最长路

• 状态：
• 状态转移方程：
• 边界：
• 结果：

（8）01 背包问题

• 状态： 令 dp i v 表示前 i 件物品 ( 1 <= i <= n，0 <= v <= v) 恰好装入背包容量为 v 的背包中所能获得的最大价值。
• 状态转移方程：

  dp[i][v] = max(dp[i-1][v], dp[i-1][v-w[i]] + c[i]); //(1 <= i <= n, w[i] <= v <= v)，这是使用二维动态数组的情况，这里逆序或者顺序都无所谓。
  dp[v] = max(dp[v], dp[v-w[i]] + c[i]) //(i <= i<= n, w[i] <= v <= v)，这是使用一维动态数组的情况，枚举方向改变为 i 从 1 到 n, v 从 v 到 0(逆序)。
  //v 的枚举顺序变为从右往左，dp[i][v] 右边的部分为刚计算过的需要保存给下一行使用的数据，而 dp[i][v] 左边的部分为当前需要使用的上一行保存的数据，这里的数组称为滚动数组。
  //特别说明：如果是用二维数组存放， v 的枚举是顺序还是逆序都无所谓；如果使用一维数组存放，则 v 的枚举必须是逆序！
  //01 背包中的每个物品都可以看作一个阶段，这个阶段中的状态有 dp[i][0]~dp[i][v]，它们均由上一个阶段的状态得到。
  //事实上，对能够划分阶段的问题来说，都可以尝试把阶段作为状态的一维，这可以使我们更方便地得到满足无后效性的状态。
  //如果当前设计的状态不满足无后效性，那么不妨把状态进行升维，即增加一维或若干维来表示相应的信息，这样可能就满足无后效性了。
  

• 边界： dp 0 v = 0 (0 <= v <= v)
• 结果： 由于 dp i v 表示的是恰好为 v 的情况，所以需要枚举 dp n v (0 <= v <= v)，取其最大值才是最后的结果。（我感觉最后的 dp n v 就是最大值了）。

（9）完全背包问题

• 状态： 令 dp i v 表示前 i 件物品恰好放入容量为 v 的背包中能获得最大价值。

• 状态转移方程：

  dp[i][v] = max(dp[i-1][v], dp[i][v-w[i]] + c[i])//(1 <= i <= n, w[i] <= v <= v)
  //其实唯一的区别就在于 max 的第二个参数是 dp[i] 而不是 dp[i-1]。
  dp[v] = max(dp[v], dp[v-w[i]] + c[i]) //(i <= i<= n, w[i] <= v <= v)，这是使用一维动态数组的情况，枚举方向改变为 i 从 1 到 n, v 从 0 到 v(顺序)。
  //求解 dp[i][v] 需要它左边的 dp[i][v-w[i]] 和 它上方的 dp[i-1][v]，显然如果让 v 从小到大枚举，dp[i][v-w[i]] 就总是已经计算出来的结果；而计算出来 dp[i][v]之后 dp[i-1][v] 就再也用不到了，可以直接覆盖掉。
  

• 边界： dp 0 v = 0 (0 <= v <= v)

• 结果： 由于 dp i v 表示的是恰好为 v 的情况，所以需要枚举 dp n v (0 <= v <= v)，取其最大值才是最后的结果。（我感觉最后的 dp n v 就是最大值了）。

三、总结

• 在大多数情况下，都可以把动态规划可解的问题看作一个有向无环图（dag），图中的结点就是状态，边就是状态转移的方向，求解问题的顺序就是按照 dag 的拓扑排序进行求解。可以通过这个角度辅助理解动态规划问题。
• 当题目与序列或字符串（记为a）有关时，可以考虑把状态设计成下面两种形式，然后根据端点特点去考虑状态转移方程。
  • 令 dp[i] 表示以 a[i] 结尾或开头的 xxxx。
  • 令dp[i][j] 表示 a[i] 至 a[j] 区间的 xxxx。
  • 其中 xxxx 均为原问题的表述。
• 分析题目中的状态需要几维来表示，然后对其中的每一维采取下面的某一个表述：
  • 恰好为 i。
  • 前 i。
• 在每一维的含义设置完毕以后，dp 数组的含义就可以设置成 “令 dp 数组表示恰好为 i （或前 i ）、恰好为 j（或前 j ）… 的 xxxx"，其中 xxxx 为原问题的描述。接下来就可以通过端点的特点去考虑状态转移方程。

四、动态规划相关的题目

1.【dp】第十四届蓝桥杯省赛c++ b组《接龙数列》（c++）

• 【代码】

  #include<bits/stdc++.h>
  using namespace std;
  
  //全局变量会赋初始值，初始值为 0
  int n, arr[10], res;
  string str;
  
  int main(){
      cin>>n;
      for(int i=0; i<n; i++){
          cin>>str;
          int a = str[0] - '0',b = str[str.size() - 1] - '0';
          int f = arr[a] + 1;
          arr[b] = max(arr[b], f);
          res = max(res, f);
      }
      cout<<n-res;
      return 0;
  }
  

五、参考

[1]. 第十四届蓝桥杯省赛c++ b组所有题目以及题解（c++）【编程题均通过100%测试数据】