动态规划（英语：Dynamic programming，简称DP）是一种在数学、管理科学、计算机科学、经济学和生物信息学中使用的，通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。
动态规划常常适用于有重叠子问题和最优子结构（英语：Optimal substructure）性质的问题，动态规划方法所耗时间往往远少于朴素解法。
动态规划背后的基本思想非常简单。大致上，若要解一个给定问题，我们需要解其不同部分（即子问题），再根据子问题的解以得出原问题的解。
通常许多子问题非常相似，为此动态规划法试图仅仅解决每个子问题一次，从而减少计算量：一旦某个给定子问题的解已经算出，则将其记忆化存储，以便下次需要同一个子问题解之时直接查表。这种做法在重复子问题的数目关于输入的规模呈指数增长时特别有用。
适用情况
- 最优子结构性质。如果问题的最优解所包含的子问题的解也是最优的，我们就称该问题具有最优子结构性质（即满足最优化原理）。最优子结构性质为动态规划算法解决问题提供了重要线索。
- 无后效性。即子问题的解一旦确定，就不再改变，不受在这之后、包含它的更大的问题的求解决策影响。
- 子问题重叠性质。子问题重叠性质是指在用递归算法自顶向下对问题进行求解时，每次产生的子问题并不总是新问题，有些子问题会被重复计算多次。动态规划算法正是利用了这种子问题的重叠性质，对每一个子问题只计算一次，然后将其计算结果保存在一个表格中，当再次需要计算已经计算过的子问题时，只是在表格中简单地查看一下结果，从而获得较高的效率，降低了时间复杂度。
实例
- 切割钢条问题
- FLoyd 最短路径
- 最大不下降序列
- 矩阵链乘
- 凸多边形三角剖分
- 0-1 背包
- 最长公共子序列
- 最优二分搜索树
动态规划的三个特点：
- 存在「重叠子问题」：当处理规模为 的问题时，中间可能需要处理多个相同且规模为 的问题
- 具备「最优子结构」：问题 ，问题 的最优解当且仅当问题 为最优解时取得；换句话说，我们可以通过求子问题 的最优解，来得到问题 的最优解
- 正确的「状态转移方程」
由于存在「重叠子问题」，所以我们可以通过「备忘录」或者「DP table」来优化穷举过程，避免不必要的计算
斐波那契数列
动态规划 DP table
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
|
/**
* 动态规划 DP table
*
* <p>time: O(n) space: O(n)
*
* @author Ethan Wang
*/
public class TabulatedSolution implements Fibonacci {
@Override
public long fib(int n) {
if (n <= 1) {
return n;
}
long[] table = new long[n + 1];
table[1] = 1;
table[2] = 1;
for (int i = 3; i <= n; i++) {
table[i] = table[i - 1] + table[i - 2];
}
return table[n];
}
}
|
递归解法
1
2
3
4
5
6
7
8
9
10
|
public class Recursion implements Fibonacci {
@Override
public long fib(int n) {
if (n <= 1) {
return n;
}
return fib(n - 1) + fib(n - 2);
}
}
|
带备忘录的递归解法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
|
/**
* 带备忘录的递归解法 Memoization
*
* <p>可以用二叉树分析 O(n) time O(n) space
*
* @author Ethan Wang
*/
public class MemoizedSolution implements Fibonacci {
@Override
public long fib(int n) {
if (n <= 1) {
return n;
}
long[] memos = new long[n + 1];
return helper(n, memos);
}
private long helper(int n, long[] memos) {
if (n <= 1) {
return n;
}
// n in memos
if (memos[n] != 0) {
return memos[n];
}
memos[n] = helper(n - 1, memos) + helper(n - 2, memos);
return memos[n];
}
}
|
尾递归
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
/**
* 尾递归 有着与 CircleRolling 相同的计算性能， 也有着递归的数学表达能力
*
* @author Ethan Wang
*/
public class TailRecursion implements Fibonacci {
@Override
public long fib(int n) {
if (n < 2) {
return n;
}
// 尾递归 Java 不支持命名参数，默认参数值 所以模仿 柯里化
return fibTail(n, 0L, 1L);
}
private long fibTail(int n, long res1, long res2) {
if (n == 0) {
return res1;
}
return fibTail(n - 1, res2, res1 + res2);
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
|
/**
* 递推 时间复杂度 O(n) 额外空间 O(1)
*
* @author Ethan Wang
*/
public class CircleRolling implements Fibonacci {
@Override
public long fib(int n) {
if (n == 0) {
return 0;
}
long a = 0L;
long b = 1L;
long c;
for (int i = 2; i <= n; i++) {
c = a + b;
a = b;
b = c;
}
return b;
}
}
|
零钱兑换
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
private int dp(int[] coins, int amount) {
// base case
if (amount == 0) return 0;
if (amount < 0) return -1;
// 做选择
int res = Integer.MIN_VALUE;
for (int coin : coins) {
// 计算子问题的结果
int subProblem = dp(coins, amount - coin);
// 子问题无解
if (subProblem == -1) continue;
// 在子问题中选择最优解
res = Math.min(res, subProblem + 1);
}
return res == Integer.MIN_VALUE ? -1 : res;
}
|
带备忘录的递归解法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
private int[] emeo;
public int coinChange(int[] coins, int amount) {
emeo = new int[amount + 1];
Arrays.fill(emeo, -666);
return dp(coins, amount);
}
private int dp(int[] coins, int amount) {
// base case
if (amount == 0) return 0;
if (amount < 0) return -1;
if (emeo[amount] != -666) return emeo[amount];
// 做选择
int res = Integer.MAX_VALUE;
for (int coin : coins) {
// 计算子问题的结果
int subProblem = dp(coins, amount - coin);
// 子问题无解
if (subProblem == -1) continue;
// 在子问题中选择最优解
res = Math.min(res, subProblem + 1);
}
emeo[amount] = res == Integer.MAX_VALUE ? -1 : res;
return emeo[amount];
}
|
也可以自底向上使用 DP table 来消除重叠子问题，关于「状态」「选择」和 base case 与之前没有区别，dp数组的定义和刚才dp函数类似，也是把「状态」，也就是目标金额作为变量。不过dp函数体现在函数参数，而dp数组体现在数组索引：dp数组的定义：当目标金额为i时，至少需要dp[i]枚硬币凑出
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
public class Solution {
public int coinChange(int[] coins, int amount) {
int max = amount + 1;
int[] dp = new int[amount + 1];
Arrays.fill(dp, max);
dp[0] = 0;
for (int i = 1; i <= amount; i++) {
for (int j = 0; j < coins.length; j++) {
if (coins[j] <= i) {
dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1);
}
}
}
return dp[amount] > amount ? -1 : dp[amount];
}
}
|
复杂度分析
- 时间复杂度：$O(Sn)$，其中 $S$ 是金额，n 是面额数。我们一共需要计算 $O(S)$ 个状态，$S$ 为题目所给的总金额。对于每个状态，每次需要枚举 n 个面额来转移状态，所以一共需要 $O(Sn)$ 的时间复杂度。
- 空间复杂度：$O(S)$。数组 dp 需要开长度为总金额 $S$ 的空间。
背包问题
设有 n 件物品，每件价值记为 $P_i$ ，每件重量记为 $W_{i}$，用一个最大重量为 ${\displaystyle W}$ 的背包，求装入物品的最大价值。 在总重量不超过W的前提下，我们希望总价格最高。对于 Y ≤ W，我们将在总重量不超过Y的前提下，总价格所能达到的最高值定义为A(Y)。A(W)即为问题的答案。
显然，A(Y)满足：
- A(0) = 0
- A(Y) = max { A(Y - 1), { pj + A(Y - wj) | wj ≤ Y } }
其中，$p_j$ 为第 j 种物品的价格。
对于特例0 1背包问题（即每件物品最多放1件，否则不放入）的问题，我们将在总重量不超过Y的前提下，前j种物品的总价格所能达到的最高值定义为A(j, Y)。
A(j, Y)的递推关系为：
- A(0, Y) = 0
- 如果 $w_j$ > Y, A(j, Y) = A(j - 1, Y)
- 如果 $w_j$ ≤ Y, A(j, Y) = max { A(j - 1, Y), $p_j$ + A(j - 1, Y - $w_j$)}
01背包代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
int knapsack(int totalWeight, int n, int[] weight, int[] price) {
// 定义dp数组：dp[i][j]表示背包容量为j时，前i个物品能获得的最大价值
int[][] dp = new int[n + 1][totalWeight + 1];
// 遍历物品然后遍历背包容量
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= totalWeight; j++) {
// 这种情况无法装下第 i 个物品，只能选择不装入
if (j - weight[i - 1] < 0) {
dp[i][j] = dp[i - 1][j];
} else {
// max(不装入, 装入)
dp[i][j] = Math.max(dp[i - 1][j], price[i - 1] + dp[i - 1][j - weight[i - 1]]);
}
}
}
return dp[n][totalWeight];
}
|
一维DP数组(滚动数组)
在使用二维数组的时候，递推公式：dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
其实可以发现如果把dp[i - 1]那一层拷贝到dp[i]上，表达式完全可以是：dp[i][j] = max(dp[i][j], dp[i][j - weight[i]] + value[i]);
与其把dp[i - 1]这一层拷贝到dp[i]上，不如只用一个一维数组了，只用dp[j]（一维数组，也可以理解是一个滚动数组）。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
public static void testWeightBagProblem(int[] weight, int[] value, int bagWeight){
int wLen = weight.length;
//定义dp数组：dp[j]表示背包容量为j时，能获得的最大价值
int[] dp = new int[bagWeight + 1];
//遍历顺序：先遍历物品，再遍历背包容量
for (int i = 0; i < wLen; i++){
for (int j = bagWeight; j >= weight[i]; j--){
dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
}
}
//打印dp数组
for (int j = 0; j <= bagWeight; j++){
System.out.print(dp[j] + " ");
}
}
|
- 01背包 每个物品最多选一个
- 多重背包 每个物品可以选多个
- 完全背包 每个物品不限数量
- 分组背包 按组打包，每组最多选一个
背包总结
背包递推公式
问能否能装满背包（或者最多装多少）：dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]); ，对应题目如下：
- 动态规划：416.分割等和子集
- 动态规划：1049.最后一块石头的重量 II
问装满背包有几种方法：dp[j] += dp[j - nums[i]] ，对应题目如下：
- 动态规划：494.目标和
- 动态规划：518. 零钱兑换 II
- 动态规划：377.组合总和Ⅳ
- 动态规划：70. 爬楼梯进阶版（完全背包）
问背包装满最大价值：dp[j] = max(dp[j], dp[j - weight[i]] + value[i]); ，对应题目如下：
问装满背包所有物品的最小个数：dp[j] = min(dp[j - coins[i]] + 1, dp[j]); ，对应题目如下：
- 动态规划：322.零钱兑换
- 动态规划：279.完全平方数
遍历顺序
01背包
- 二维dp数组先遍历物品还是先遍历背包都是可以的，且第二层for循环是从小到大遍历。
- 一维dp数组只能先遍历物品再遍历背包容量，且第二层for循环是从大到小遍历。
完全背包
- 纯完全背包的一维dp数组实现，先遍历物品还是先遍历背包都是可以的，且第二层for循环是从小到大遍历。
- 如果求组合数就是外层for循环遍历物品，内层for遍历背包。
- 如果求排列数就是外层for遍历背包，内层for循环遍历物品。
对于背包问题，其实递推公式算是容易的，难是难在遍历顺序上，如果把遍历顺序搞透，才算是真正理解了。
最长公共子序
最长公共子序列（LCS）是一个在一个序列集合中（通常为两个序列）用来查找所有序列中最长子序列的问题。这与查找最长公共子串的问题不同的地方是：子序列不需要在原序列中占用连续的位置 。最长公共子序列问题是一个经典的计算机科学问题，也是数据比较（英语：data comparison）程序，比如Diff工具，和生物信息学应用的基础。它也被广泛地应用在版本控制，比如Git用来调和文件之间的改变。
- text1[i−1]=text2[j−1] - dp[i][j]=dp[i-1][j-1]+1
- text1[i−1]!=text2[j−1] - dp[i][j]=max(dp[i-1][j], dp[i][j-1])
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
class Solution {
public int longestCommonSubsequence(String text1, String text2) {
int m = text1.length(), n = text2.length();
int[][] dp = new int[m + 1][n + 1];
for (int i = 1; i <= m; i++) {
char c1 = text1.charAt(i - 1);
for (int j = 1; j <= n; j++) {
char c2 = text2.charAt(j - 1);
if (c1 == c2) {
dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
return dp[m][n];
}
}
|
复杂度分析