最优子结构原理 和 DP 数组遍历方向

#算法/动态规划

目录

1. 如何判断是否复合 最优子结构

  • 找全校最高分， ==> 那么每个班的最高分，这是复合最优子结构的
  • 找全校最大分差，并不能通过找每个班最大分差来实现，这不符合最优子结构
    • 最优子结构失效情况 => 改造问题 ，即找出全校最高分 和 最低分 ，不就可以转化为第一个问题吗？

一棵二叉树的最大值，通过分解为求左右子树（子问题）的最大值，所以也是符合最优子结构的，但是它不是动态规划问题。 最优子结构是动态规划的必要条件，即动态规划一定是有最优子结构的，一定是让你求最值的。

2. 如何判断是否有重叠子问题

1、画图，递归图，看看有没有重复节点，如 fib 问题，如下图：

|544

2、通过递归框架判断，比如状态 (i, j) 转移到 (i-1, j-1) ，有几种路径？

  • 状态 (i, j) → dp(i - 1, j) → dp(i - 1, j - 1)
  • 状态 (i, j) → dp(i, j - 1) → dp(i - 1, j - 1)

|552

所以 dp(i-1, j-1) 会被多次计算，一定存在 重叠子问题，可以通过 「备忘录」或者「DP table」 来优化。

3. 为什么经常看到将 dp 数组的大小设置为 n + 1 而不是 n ?

  • 其实 dp数组大小设置多大，取决于是否能够正确处理 base case ,
  • 另外，其实设置大一点也是可以的。

4. 为什么动态规划遍历 dp 数组的方式五花八门，有的正着遍历，有的倒着遍历，有的斜着遍历。

其实只需要关注两点：

1、遍历的过程中，所需的状态必须是已经计算出来的。 2、遍历结束后，存储结果的那个位置必须已经被计算出来。

比如还是 10. 子序列：最小编辑距离 的示例，dp[m][n] 结果是通过 dp[i-1][j], dp[i][j-1], dp[i-1][j-1] 转移而来，所以肯定是正着遍历 ，如下图：

|600

5. 参考