Algorithm进阶计划 -- 动态规划（上）
动态规划
- 动态规划的基本原理
- 动态规划的运用
图片来源于网络
1. 动态规划的基本原理
动态规划（Dynamic Programming，简称 DP），是运筹学的一个分支，是求解决策过程最优化的过程 。
动态规划是在20世纪50年代初，美国数学家贝尔曼等人在研究多阶段决策过程的优化问题时，提出的最优化原理，它在计算机问题上应用比较多，比如求最长递增子序列，最小编辑距离等等。
动态规划问题的一般形式就是求最值。而求解动态规划的核心问题是穷举：
- 动态规划的穷举有点特别，因为这类问题存在重叠子问题，如果暴力穷举的话效率会极其低下，所以需要「备忘录」或者「DP table」来优化穷举过程，避免不必要的计算。
- 动态规划问题一定会具备最优子结构，才能通过子问题的最值得到原问题的最值。
- 动态规划的核心思想是穷举求最值，但问题千变万化，穷举所有可行解并不是一件容易的事，只有列出正确的状态转移方程才能正确的穷举。
上面提到的重叠子问题、最优子结构、状态转移方程就是动态规划三要素。
在实际算法问题中，写出状态转移方程是最困难的，可以参考如下思维框架来辅助思考状态转移方程：
明确「状态」 -> 定义 dp 数组/函数的含义 -> 明确「选择」-> 明确 base case。
接下来通过几个简单的例子来了解动态规划的基本原理。
1.1 斐波那契数列
斐波那契数列定义如下：
斐波那契数列
斐波那契数列的例子严格来说不算动态规划，因为没有涉及求最值，以下旨在演示算法设计螺旋上升的过程。
1.1.1 暴力递归
斐波那契数列的数学形式就是递归的，直接写代码代如下：
/**
* 暴力递归
*/
int fib(int n) {
if (n == 0) return 0;
if (n == 1 || n == 2) return 1;
return fib(n - 1) + fib(n - 2);
}
上面代码简洁易懂，但非常低效，其算法的时间复杂度为 O(2^n)，指数级别。
如 n = 20，上面算法递归树如下：
递归树
可以发现存在大量重复计算，如 f(18) 被计算了两次，而以它为根的这个递归树体量巨大，因此算法及其低效。
这就是动态规划问题的第一个性质：重叠子问题。
1.1.2 带备忘录的递归解法
解决重复计算问题，可以添加个「备忘录」，每次算出某个子问题的答案后，先记到「备忘录」里再返回；每次遇到一个子问题先去「备忘录」里查找，若发现已经计算过这个问题就直接拿出来用。
使用一个数组或哈希表充当备忘录如下：
/**
* 带备忘录的递归解法
*/
int fib(int n) {
if (n < 1) return 0;
int[] memo = new int[n];
for (int i = 0; i < n; i++) {
memo[i] = 0;
}
return helper(memo, n);
}
/**
* 添加到备忘录 or 在备忘录中查找
*/
int helper(int[] memo, int n) {
// base case
if (n == 1 || n == 2) return 1;
// 已经计算过
if (memo[n - 1] != 0) return memo[n - 1];
// 若没计算过则添加到备忘录
memo[n - 1] = helper(memo, n - 1) + helper(memo, n - 2);
return memo[n - 1];
}
其递归树如下：
带备忘录的递归树
上面相当于把一棵存在巨量冗余的递归树通过「剪枝」，改造成了一幅不存在冗余的递归图，减少子问题的个数：
自顶向下递归图
子问题个数为 O(n)，而处理子问题的时间为 O(1)，因此算法的时间复杂度为 O(n)。
至此，带备忘录的递归解法的效率就和迭代的动态规划一样了。它和迭代的动态规划思想差不多，区别是这种方法是自顶向下，而动态规划是自底向上。
-
自顶向下 是从上向下延伸，比如从
f(20)向下逐渐分解规模，直到f(1)和f(2)触底，然后逐层返回答案。 -
自底向上 是从最底下向上延伸，比如从规模最小的
f(1)和f(2)开始往上推，直到推到想要的答案f(20)。这也就是为什么动态规划一般都脱离了递归，而是由循环迭代完成计算。
1.1.3 dp 数组的迭代解法
有了上面「备忘录」的启发，可以把这个「备忘录」独立出来成为一张表（DP table），在这张表上完成「自底向上」的推算：
/**
* 动态规划：自底向上
*/
int fib(int n) {
if (n < 1) return 0;
if (n == 1 || n == 2) return 1;
int[] dp = new int[n + 1];
for (int i = 0; i < n + 1; i++) {
dp[i] = 0;
}
// base case
dp[1] = dp[2] = 1;
for (int i = 3; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}
上面的 DP table 图如下：
DP table 图
上面可以发现 DP table 很像之前那个「剪枝」后的结果，只是反过来算而已。而状态转移方程就是描述问题的数学形式：
状态转移方程
比如，把 f(n) 想做一个状态 n，这个状态 n 是由状态 n - 1 和状态 n - 2 相加转移而来，这就叫状态转移。
列出「状态转移方程」是解决动态规划问题的核心，而状态转移方程直接代表着暴力解法，优化方法无非是用备忘录或者 DP table。
当然，这边的例子还可以进一步优化，把空间复杂度降为 O(1)：
/**
* 根据斐波那契数列的状态转移方程，当前状态只和之前的两个状态有关，
* 因此只需存储之前的两个状态就行了。
*/
int fib(int n) {
if (n < 1) return 0;
if (n == 1 || n == 2) return 1;
int prev = 1, curr = 1;
for (int i = 3; i <= n; i++) {
int sum = prev + curr;
prev = curr;
curr = sum;
}
return curr;
}
1.2 零钱兑换问题
零钱兑换定义如下：
零钱兑换
1.2.1 暴力递归
上面的问题是动态规划问题，因为它具有「最优子结构」。要符合「最优子结构」，子问题间必须互相独立。
如想求 amount = 11 时的最少硬币数（原问题），若知道凑出 amount = 10 的最少硬币数（子问题），只需把子问题的答案加一（再选一枚面值为 1 的硬币）就是原问题的答案，因为硬币的数量是没有限制的，子问题之间没有相互制，是互相独立的。
暴力解法如下：
/**
* 零钱兑换：暴力递归解法
*
* @param coins 可选硬币面值
* @param amount 目标金额
*/
public int coinChange(int[] coins, int amount) {
// 如何列出正确的状态转移方程?
// 1. 确定「状态」，也就是原问题和子问题中变化的变量。由于硬币数量无限，所以唯一的状态就是目标金额amount。
// 2. 确定dp函数的定义：函数 dp(n)表示，当前的目标金额是n，至少需要dp(n)个硬币凑出该金额。
// 3. 确定「选择」并择优，也就是对于每个状态，可以做出什么选择改变当前状态。
// 4. 明确 base case，显然目标金额为 0 时，所需硬币数量为 0；当目标金额小于 0 时，无解，返回 -1
// 要求目标金额是 amount
return dp(coins, amount);
}
/**
* 要凑出金额 n，至少要 dp(n) 个硬币
*/
private int dp(int[] coins, int n) {
// base case
if (n == 0) return 0;
if (n < 0) return -1;
int res = Integer.MAX_VALUE;
for (int coin : coins) {
int child = dp(coins, n - coin);
if (child == -1) continue; // 子问题无解，跳过
res = Math.min(res, 1 + child); // 做选择，需要硬币最少的那个结果就是答案
}
return res == Integer.MAX_VALUE ? -1 : res;
}
上面代码的数学形式就是状态转移方程：
状态转移方程
其递归树如下：
递归树
时间复杂度分析：子问题总数 x 解决每个子问题的时间。
子问题总数为递归树节点个数，是 O(n^k)；每个子问题中含有一个 for 循环，复杂度为 O(k)。即总时间复杂度为 O(k * n^k)，指数级别。
接下来需要消除一下重叠子问题。
1.2.2 带备忘录的递归
只需要稍加修改，就可以通过备忘录消除子问题：
/**
* 带备忘录的递归解法
*/
public int coinChange(int[] coins, int amount) {
// 备忘录
HashMap<Integer, Integer> memo = new HashMap<>();
return dp(coins, amount, memo);
}
private int dp(int[] coins, int n, HashMap<Integer, Integer> memo) {
// 查备忘录，避免重复计算
if (memo.containsKey(n)) return memo.get(n);
if (n == 0) return 0;
if (n < 0) return -1;
int res = Integer.MAX_VALUE;
for (int coin : coins) {
int child = dp(coins, n - coin, memo);
if (child == -1) continue;
res = Math.min(res, 1 + child);
}
// 记入备忘录
memo.put(n, res == Integer.MAX_VALUE ? -1 : res);
return memo.get(n);
}
上面「备忘录」减小了子问题数目，消除了子问题的冗余，即子问题数目为 O(n)，处理一个子问题的时间是 O(k)，所以总的时间复杂度是 O(kn)。
1.2.3 dp 数组的迭代解法
若自底向上使用 dp table 来消除重叠子问题，dp 数组的定义和刚才 dp 函数类似：
dp[i] = x 表示，当目标金额为 i 时，至少需要 x 枚硬币。
代码如下：
/**
* 动态规划：dp 数组的迭代解法
*/
public int coinChange(int[] coins, int amount) {
// 数组大小为 amount + 1，初始值也为 amount + 1
int[] dp = new int[amount + 1];
for (int i = 0; i <= amount; i++) {
// 初始化为amount + 1就相当于初始化为正无穷，便于后续取最小值
dp[i] = amount + 1;
}
// base case
dp[0] = 0;
for (int i = 0; i < dp.length; i++) {
// 内层 for 在求所有子问题 + 1 的最小值
for (int coin : coins) {
// 子问题无解，跳过
if (i - coin < 0) continue;
dp[i] = Math.min(dp[i], 1 + dp[i - coin]);
}
}
return dp[amount] == amount + 1 ? -1 : dp[amount];
}
上面的 DP table 图如下：
DP table 图
小结：
斐波那契数列，解释了如何通过「备忘录」或者「dp table」的方法来优化递归树，并且明确了这两种方法本质上是一样的，只是自顶向下和自底向上的不同。
零钱兑换问题，展示了如何流程化确定「状态转移方程」，只要通过状态转移方程写出暴力递归解，剩下的也就是优化递归树，消除重叠子问题。
2. 动态规划的运用
2.1 最小路径和
2.1.1 最小路径和
力扣 64 题如下：
最小路径和
一般来说，在二维矩阵中求最优化问题（最大值或最小值），肯定需要递归 + 备忘录，也就是动态规划技巧。
首先，定义一个 dp 函数：从左上角位置 (0, 0) 走到位置 (i, j) 的最小路径和为 dp(grid, i, j)。根据这个定义，可以写出如下主函数逻辑：
/**
* 路径最小和
*/
public int minPathSum(int[][] grid) {
int m = grid.length;
int n = grid[0].length;
// 计算从左上角走到右下角的最小路径和
return dp(grid, m - 1, n - 1);
}
接着，dp(grid, i, j) 的值取决于 dp(grid, i - 1, j) 和 dp(grid, i, j - 1)，实现 dp 函数如下：
/**
* 从左上角位置 (0, 0) 走到位置 (i, j) 的最小路径和为 dp(grid, i, j)
*/
private int dp(int[][] grid, int i, int j) {
// 非法索引检查
// 如果索引出界，返回一个很大的值，保证在取 min 的时候不会被取到
if (i < 0 || j < 0) return Integer.MAX_VALUE;
// base case
if (i == 0 && j == 0) return grid[i][j];
// 左边和上面的最小路径和加上 grid[i][j] 就是到达 (i, j) 的最小路径和
return grid[i][j] + Math.min(dp(grid, i - 1, j), dp(grid, i, j - 1));
}
以上便是暴力穷举法。
最后，用备忘录的方法消除重叠子问题，如下：
/**
* 路径最小和
*/
public int minPathSum(int[][] grid) {
int m = grid.length;
int n = grid[0].length;
// 备忘录
int[][] memo = new int[m][n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
memo[i][j] = -1; // 初始值全部设为 -1
}
}
// 计算从左上角走到右下角的最小路径和
return dp2(memo, grid, m - 1, n - 1);
}
/**
* 从左上角位置 (0, 0) 走到位置 (i, j) 的最小路径和为 dp(grid, i, j)
*/
private int dp2(int[][] memo, int[][] grid, int i, int j) {
// base case
if (i == 0 && j == 0) return grid[i][j];
// 如果索引出界，返回一个很大的值，保证在取 min 的时候不会被取到
if (i < 0 || j < 0) return Integer.MAX_VALUE;
// 查找备忘录
if (memo[i][j] != -1) return memo[i][j];
// 添加到备忘录
memo[i][j] = grid[i][j] + Math.min(dp2(memo, grid, i - 1, j), dp2(memo, grid, i, j - 1));
return memo[i][j];
}
至此，本题就算是解完了，时间复杂度和空间复杂度都是O(MN)，标准的自顶向下动态规划解法。
当然，也可以用自底向上的迭代解法来解，如下：
/**
* 路径最小和 -- 自底向上迭代
*/
public int minPathSum2(int[][] grid) {
int m = grid.length;
int n = grid[0].length;
// 定义dp数组：从左上角位置(0, 0)走到位置(i, j)的最小路径和为dp[i][j]
int[][] dp = new int[m][n];
// base case
dp[0][0] = grid[0][0];
// 根据dp数组的定义：dp[i][0] = sum(grid[0..i][0]), dp[0][j] = sum(grid[0][0..j])
for (int i = 1; i < m; i++) {
dp[i][0] = dp[i - 1][0] + grid[i][0];
}
for (int j = 1; j < n; j++) {
dp[0][j] = dp[0][j - 1] + grid[0][j];
}
// 状态转移
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
dp[i][j] = grid[i][j] + Math.min(dp[i - 1][j], dp[i][j - 1]);
}
}
return dp[m - 1][n - 1];
}
2.1.2 下降路径最小和
力扣 931 题如下：
下降路径最小和
首先，定义一个 dp 函数：从第一行 matrix[0][..] 向下落，落到位置 matrix[i][j] 的最小路径和为dp(matrix, i, j)。根据这个定义，可以写出如下主函数逻辑：
/**
* 下降路径最小和
*/
public int minFallingPathSum(int[][] matrix) {
int n = matrix.length;
int res = Integer.MAX_VALUE;
// 终点可能在最后一行的任意一列
for (int j = 0; j < n; j++) {
// 最后一行为 n-1
res = Math.min(res, dp(matrix, n - 1, j));
}
return res;
}
接着，只要知道到达 (i-1, j), (i-1, j-1), (i-1, j+1) 这三个位置的最小路径和，加上 matrix[i][j] 的值，即可计算出到达位置 (i, j) 的最小路径和：
/**
* 从第一行 matrix[0][..] 向下落，落到位置 matrix[i][j] 的最小路径和为 dp(matrix, i, j)
*/
private int dp(int[][] matrix, int i, int j) {
// 非法索引检查
if (i < 0 || j < 0 || i >= matrix.length || j >= matrix[0].length) {
return Integer.MAX_VALUE;// 返回一个特殊值
}
// base case
if (i == 0) return matrix[i][j];
// 状态转移
return matrix[i][j] + min(
dp(matrix, i - 1, j),
dp(matrix, i - 1, j - 1),
dp(matrix, i - 1, j + 1));
}
/**
* 求 a、b、c 的最小值
*/
private int min(int a, int b, int c) {
return Math.min(a, Math.max(b, c));
}
以上便是暴力穷举法。
最后，用备忘录的方法消除重叠子问题，如下：
/**
* 下降路径最小和
*/
public int minFallingPathSum(int[][] matrix) {
int n = matrix.length;
int res = Integer.MAX_VALUE;
// 备忘录
int[][] memo = new int[n][n];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
memo[i][j] = 666666;// 备忘录里的值初始化在[-10000, 10000] 之外即可
}
}
// 终点可能在最后一行的任意一列
for (int j = 0; j < n; j++) {
res = Math.min(res, dp(memo, matrix, n - 1, j));
}
return res;
}
/**
* 从第一行 matrix[0][..] 向下落，落到位置 matrix[i][j] 的最小路径和为 dp(matrix, i, j)
*/
private int dp(int[][] memo, int[][] matrix, int i, int j) {
// 1. 非法索引检查
if (i < 0 || j < 0 || i >= matrix.length || j >= matrix[0].length) {
return 999999;// 返回一个特殊值
}
// 2. base case
if (i == 0) return matrix[i][j];
// 3. 查找备忘录，防止重复计算
if (memo[i][j] != 66666) {
return memo[i][j];
}
// 进行状态转移，添加到备忘录
memo[i][j] = matrix[i][j] + min(
dp(memo, matrix, i - 1, j),
dp(memo, matrix, i - 1, j - 1),
dp(memo, matrix, i - 1, j + 1));
return memo[i][j];
}
/**
* 求 a、b、c 的最小值
*/
private int min(int a, int b, int c) {
return Math.min(a, Math.max(b, c));
}
注：做题时，除了题意本身，一定不要忽视题目给定的其他信息。
比如，上面的测试用理数据范围可以确定「什么是特殊值」。除此之外，数据范围还可以帮助估算算法的时间/空间复杂度；
比如，有的算法题，只想到一个暴力求解的思路，但题目给定的数据量很大，就说明这个求解思路存在优化的空间；
比如，题目限制算法复杂度是 O(NlogN)，可以想到用二分搜索或二叉树相关的数据结构，类似 TreeMap，PriorityQueue 等；
比如，题目限制算法复杂度是 O(MN)，可以想到常规解法是用回溯算法暴力穷举，更好的解法是动态规划。
2.2 编辑距离
力扣 72 题如下：
编辑距离
解决两个字符串的动态规划问题，一般都是用两个指针 i ，j 分别指向两个字符串的最后，然后一步步往前走，缩小问题的规模。
对于上面题目，解题思路：base case 是 i 走完 s1(word1) 或 j 走完 s2(word2)，可以直接返回另一个字符串剩下的长度，而每对字符 s1[i] 和 s2[j]，可以有以下操作：
if s1[i] == s2[j]:
啥都不做（skip）
i, j 同时向前移动
else:
3选1：插入、删除、替换
首先，定义一个 dp 函数：s1[0..i] 和 s2[0..j] 的最小编辑距离为 dp(i, j)。根据这个定义，可以写出如下主函数逻辑：
/**
* 最小编辑距离
*/
public int minDistance(String s1, String s2) {
// i , j 初始化指向最后一个索引
return dp(s1.length() - 1, s2.length() - 1);
}
接着，实现 dp 函数：
/**
* 定义：返回 s1[0..i] 和 s2[0..j] 的最小编辑距离
*/
private int dp(String s1, String s2, int i, int j) {
// base case
if (i == -1) return j + 1;
if (j == -1) return i + 1;
if (s1.charAt(i) == s2.charAt(j)) {
// 本来就相等，不需要任何操作
// 此时 s1[0..i] 和 s2[0..j] 的最小编辑距离等于 s1[0..i-1] 和 s2[0..j-1] 的最小编辑距离
// 即 dp(i, j) 等于 dp(i-1, j-1)
return dp(s1, s2, i - 1, j - 1);
} else {
return min(
// 插入：在 s1[i] 插入一个和 s2[j] 一样的字符，那么 s2[j] 就被匹配了，前移 j，继续跟 i 对比，操作数 + 1
dp(s1, s2, i, j - 1) + 1,
// 删除：把 s[i] 这个字符删掉，前移 i，继续跟 j 对比，操作数 + 1
dp(s1, s2, i - 1, j) + 1,
// 替换：把 s1[i] 替换成 s2[j]，这样它俩就匹配了，同时前移 i、 j 继续对比，操作数 + 1
dp(s1, s2, i - 1, j - 1) + 1
);
}
}
以上便是暴力穷举法。
最后，用备忘录的方法消除重叠子问题，如下：
/**
* 最小编辑距离 -- 备忘录
*/
public int minDistance2(String s1, String s2) {
int m = s1.length();
int n = s2.length();
// 备忘录
int[][] memo = new int[m][n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
memo[i][j] = -1;
}
}
// i , j 初始化指向最后一个索引
return dp(memo, s1, s2, m - 1, n - 1);
}
/**
* 定义：返回 s1[0..i] 和 s2[0..j] 的最小编辑距离
*/
private int dp(int[][] memo, String s1, String s2, int i, int j) {
// base case
if (i == -1) return j + 1;
if (j == -1) return i + 1;
// 备忘录中查找
if (memo[i][j] != -1) return memo[i][j];
// 添加到备忘录
if (s1.charAt(i) == s2.charAt(j)) {
memo[i][j] = dp(memo, s1, s2, i - 1, j - 1);
} else {
memo[i][j] = min(
dp(memo, s1, s2, i, j - 1) + 1, // 插入
dp(memo, s1, s2, i - 1, j) + 1, // 删除
dp(memo, s1, s2, i - 1, j - 1) + 1 // 替换
);
}
return memo[i][j];
}
/**
* 求 a、b、c 的最小值
*/
private int min(int a, int b, int c) {
return Math.min(a, Math.max(b, c));
}
当然，也可以用 DP table 来解，如下：
/**
* 最小编辑距离 -- DP table
*/
public int minDistance3(String s1, String s2) {
int m = s1.length();
int n = s2.length();
// 定义dp数组：存储 s1[0..i] 和 s2[0..j] 的最小编辑距离
int[][] dp = new int[m + 1][n + 1];
// base case
for (int i = 1; i <= m; i++) {
dp[i][0] = i;
}
for (int j = 1; j <= n; j++) {
dp[0][j] = j;
}
// 状态转移，自底向上求解
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
dp[i][j] = dp[i - 1][j - 1];
} else {
dp[i][j] = min(
dp[i - 1][j] + 1,
dp[i][j - 1] + 1,
dp[i - 1][j - 1] + 1
);
}
}
}
// 存储着整个 s1 和 s2 的最小编辑距离
return dp[m][n];
}
/**
* 求 a、b、c 的最小值
*/
private int min(int a, int b, int c) {
return Math.min(a, Math.max(b, c));
}
小结：
算法设计无非就是先思考“如何穷举”，然后再追求“如何聪明地穷举”。
列出动态转移方程，就是在解决“如何穷举”的问题。
备忘录、DP table 就是在追求“如何聪明地穷举”。
用空间换时间的思路，是降低时间复杂度的不二法门。
参考链接：
