动态规划

1. 思想简介

动态规划不是某一种具体的算法，而是一种算法思想：若要解一个给定问题，我们需要解其不同部分（即子问题），再根据子问题的解以得出原问题的解。

应用这种算法思想解决问题的可行性，对子问题与原问题的关系，以及子问题之间的关系这两方面有一些要求，它们分别对应了最优子结构和重复子问题。

1.1 最优子结构

即从很多解决问题的方案中找到最优的一个。当我们在求一个问题最优解的时候，如果可以把这个问题分解成多个子问题，然后递归地找到每个子问题的最优解，最后通过一定的数学方法对各个子问题的最优解进行组合得出最终的结果。

1.2 重复子问题

当我们在递归地寻找每个子问题的最优解的时候，有可能会会重复地遇到一些更小的子问题，而且这些子问题会重叠地出现在子问题里，出现这样的情况，会有很多重复的计算，动态规划可以保证每个重叠的子问题只会被求解一次。当重复的问题很多的时候，动态规划可以减少很多重复的计算。

1.3 核心

解决动态规划问题的核心：找出子问题及其子问题与原问题的关系

2. 贪心、分治与动态规划

2.1 分治

解决分治问题的时候，思路就是想办法把问题的规模减小，有时候减小一个，有时候减小一半，然后将每个小问题的解以及当前的情况组合起来得出最终的结果。例如归并排序和快速排序，归并排序将要排序的数组平均地分成两半，快速排序将数组随机地分成两半。然后不断地对它们递归地进行处理。

这里存在有最优的子结构，即原数组的排序结果是在子数组排序的结果上组合出来的，但是不存在重复子问题，因为不断地对待排序的数组进行对半分的时候，两半边的数据并不重叠，分别解决左半边和右半边的两个子问题的时候，没有子问题重复出现，这是动态规划和分治的区别。

2.2 贪心

• 关于最优子结构

  • 贪心：每一步的最优解一定包含上一步的最优解，上一步之前的最优解无需记录
  • 动态规划：全局最优解中一定包含某个局部最优解，但不一定包含上一步的局部最优解，因此需要记录之前的所有的局部最优解

• 关于子问题最优解组合成原问题最优解的组合方式

  • 贪心：如果把所有的子问题看成一棵树的话，贪心从根出发，每次向下遍历最优子树即可，这里的最优是贪心意义上的最优。此时不需要知道一个节点的所有子树情况，于是构不成一棵完整的树
  • 动态规划：动态规划需要对每一个子树求最优解，直至下面的每一个叶子的值，最后得到一棵完整的树，在所有子树都得到最优解后，将他们组合成答案

• 结果正确性

  • 贪心不能保证求得的最后解是最佳的，复杂度低
  • 动态规划本质是穷举法，可以保证结果是最佳的，复杂度高

子项	分治	动态规划	贪心
适用类型	通用	优化	优化
子问题	每个都不同	有很多重复	只有一个
最优子结构	没有要求	必须满足	必须满足
子问题数	全部都要解	全部都要解	只解一个

3. 分类

3.1 线性动态规划

线性动态规划的主要特点是状态的推导是按照问题规模 i 从小到大依次推过去的，较大规模的问题的解依赖较小规模的问题的解。

状态定义：

dp[n] := [0..n] 上问题的解

状态转移：

dp[n] = f(dp[n-1], ..., dp[0])

3.2 单串

单串 dp[i] 线性动态规划最简单的一类问题，输入是一个串，状态一般定义为 dp[i] := 考虑[0..i]上，原问题的解，其中 i 位置的处理，根据不同的问题，主要有两种方式：

• 第一种是 i 位置必须取，此时状态可以进一步描述为 dp[i] := 考虑[0..i]上，且取 i，原问题的解；
• 第二种是 i 位置可以取可以不取

大部分的问题，对 i 位置的处理是第一种方式，例如力扣：

• 70 爬楼梯问题
• 801 使序列递增的最小交换次数
• 790 多米诺和托米诺平铺
• 746 使用最小花费爬楼梯

状态转移

1. 依赖比 i 小的 O(1) 个子问题
   • dp[i] = f(dp[i - 1])
   • 空间复杂度 O(n)O(n)O(n) 可以优化为 O(1)
2. 依赖比 i 小的 O(n) 个子问题
   • dp[i] = f(dp[i - 1], dp[i - 2], ..., dp[0])
   • f 常见的有 max/min
   • 可能还会对 i-1,i-2,...,0 有一些筛选条件