动态规划介绍

动态规划刷题流程

1. 确定 dp 数组以及下标的含义（设计状态）

   一般 dp 数组的定义直接对标问题的解，听起来很抽象，但是多做几个题目就知道这句话的含义了😂

2. 确定状态转移方程（递推公式）

   即如何由 dp[i-1] 或 dp[i-2] 推导出 dp[i]，或者说是如何写出递推公式（这里以一维数组为例，二维数组是类似的）

3. 确定 dp 数组初始状态（边界条件）

   也就是 dp 数组的初始化，这很可能根据状态转移方程来确定，所以将这一步放在第二步之后

4. 确定 dp 数组遍历顺序

   是从左到右还是从上到下，是从左上往右下还是从右下往左上遍历呢

5. 返回最终的解

   最终的解一般是 dp 数组的最后一项，但这并不是绝对的。这主要还是得根据第一步来确定，也就是说最终的解是根据 dp 数组的含义来决定的

   比如 最长重复子数组 最终的解就不是 dp 数组的最后一项，而 最长公共子序列 最终的解就是 dp 数组的最后一项。而导致这两个问题最终解不同的原因就是它们在第一步状态设计的就不一样

   最长重复子数组的状态设计为： $dp[i][j]$ 表示数组 $nums1$、$nums2$ 分别在索引范围 $0～i-1、0～j-1$，并且以 $nums1[i-1]，nums2[j-1]$ 结尾的公共的、长度最长的子数组（$nums1[i-1]==nums2[j-1]$）的长度（若为$0$，说明 $nums1[i-1]!=nums2[j-1]$）

   最长重复子数组的状态设计的最后一项并不对标问题的解

   最长公共子序列的状态设计为： $dp[i][j]$ 表示 $text1、text2$ 分别在索引范围 $0～i-1、0～j-1$ 范围内的最长公共子序列的长度

   最长公共子序列的状态设计的最后一项直接对标问题的解，所以直接返回最后一项

动态规划思考

1. 空间压缩

   空间压缩也叫状态压缩，可以起到节省空间（降低空间复杂度）的效果，如斐波那契额数列的迭代解法

2. 状态记录

   避免重复计算，以起到节省时间（降低时间复杂度）的效果，如斐波那契额数列的递归解法

参考资料

• 动态规划理论基础 (opens new window)
• 夜深人静写算法（四十三）- 线性DP (opens new window)