经典动态规划
- 背包问题
- 最长子序列问题
1. 背包问题
1.1 0-1 背包问题
0-1 背包问题，描述如下：
给你一个可装载重量为 W 的背包和 N 个物品，每个物品有重量和价值两个属性。
其中第 i 个物品的重量为 wt[i]，价值为 val[i]，让你用这个背包装物品，最多能装的价值是多少？
// 输入：
N = 3, W = 4
wt = [2, 1, 3]
val = [4, 2, 3]
// 输出：
6 (解释：选择前两件物品装进背包，总重量 3 小于 W，可以获得最大价值 6)
上面是一个典型的动态规划问题，物品不可以分割，要么装进包里，要么不装，不能说切成两块装一半。
接下来按照动态规划标准套路进行演示：
第一步：要明确两点，「状态」和「选择」。
- 状态：就是 背包的容量 和 可选择的物品
- 选择：就是 装进背包 或 不装进背包
有了状态和选择，套入框架如下：
for 状态1 in 状态1的所有取值：
for 状态2 in 状态2的所有取值：
for ...
dp[状态1][状态2][...] = 择优(选择1，选择2...)
第二步：要明确 dp 数组的定义。
dp 数组是描述问题局面的一个数组，用它把状态表示出来，定义如下：
dp[i][w] 的定义：对于前 i 个物品，当前背包的容量为 w，这种情况下可以装的最大价值是 dp[i][w]。
如 dp[3][5] = 6 表示只对前 3 个物品进行选择，当背包容量为 5 时，最多可以装下的价值为 6。
根据定义，要求的最终答案就是 dp[N][W]。base case 就是 dp[0][..] = dp[..][0] = 0。（没物品或背包没空间时能装的最大价值是 0）。
细化框架如下：
int dp[N+1][W+1]
dp[0][..] = 0
dp[..][0] = 0
for i in [1..N]:
for w in [1..W]:
dp[i][w] = max(
把物品 i 装进背包,
不把物品 i 装进背包
)
return dp[N][W]
第三步：根据「选择」，思考状态转移的逻辑。
这一步要结合对 dp 数组的定义和算法逻辑来分析：
- 若没有把第
i个物品装入背包，那么最大价值dp[i][w]等于dp[i-1][w]。 - 若把第
i个物品装入了背包，那么dp[i][w]等于dp[i-1][w-wt[i-1]] + val[i-1]。
综上两种选择，进一步细化代码如下：
for i in [1..N]:
for w in [1..W]:
dp[i][w] = max(
dp[i-1][w],
dp[i-1][w - wt[i-1]] + val[i-1]
)
return dp[N][W]
最后：把伪码翻译成代码，处理一些边界情况。
这边主要处理 w - wt[i-1] 可能小于 0 导致数组索引越界的问题，如下：
/**
* 0-1 背包问题
*
* @param w 背包可装载的重量
* @param n 物品的数量
* @param wt 物品对应的重量
* @param val 物品对应的价值
*/
public int knapsack(int w, int n, int[] wt, int[] val) {
// dp[i][w]定义：对于前i个物品，当前背包的容量为w，这种情况下可以装的最大价值是dp[i][w]
int[][] dp = new int[n + 1][w + 1];
for (int i = 0; i < n; i++) {
dp[i][0] = 0;
}
for (int j = 0; j < w; j++) {
dp[0][j] = 0;
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= w; j++) {
if (j - wt[i - 1] < 0) {
// 当前背包容量装不下，只能选择不装入背包
dp[i][j] = dp[i - 1][w];
} else {
// 装入或者不装入背包，择优
dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][w - wt[i - 1] + val[i - 1]]);
}
}
}
return dp[n][w];
}
1.2 分割等和子集
力扣 416 题如下：
这道题其实就是 0-1 背包问题的变体，转化为背包问题描述如下：
给一个可装载重量为 sum/2 的背包和 N 个物品，每个物品的重量为 nums[i]。是否存在一种装法，能够恰好将背包装满？
第一步：要明确「状态」和「选择」。
- 状态： 背包的容量 和 可选择的物品
- 选择： 装进背包 或 不装进背包
第二步：要明确 dp 数组的定义。
dp[i][j] = x 表示，对于前 i 个物品，当前背包的容量为 j 时，若 x 为 true，则说明恰好能将背包装满，否则不能。
根据这个定义，要求的最终答案是 dp[N][sum/2]，base case 就是 dp[..][0] = true 和 dp[0][..] = false，即背包没空间时相当于装满了，而当没物品可选择时没办法装满背包。
第三步：根据「选择」，思考状态转移的逻辑。
根据「选择」对 dp[i][j] 得到以下状态转移：
- 不把
nums[i]算入子集(不把这第i个物品装入背包)，是否能够恰好装满背包，取决于上一个状态dp[i-1][j]。 - 把
nums[i]算入子集(把这第i个物品装入背包)，是否能够恰好装满背包，取决于状态dp[i - 1][j-nums[i-1]]。
最后：处理一些边界情况，代码实现如下：
/**
* 分割等和子集 -- 0-1 背包问题变种
* <p>
* 先对集合求和，得出 sum，给一个可装载重量为 sum/2 的背包和 N 个物品，每个物品的重量为 nums[i]。
* 是否存在一种装法，能够恰好将背包装满？
*/
public boolean canPartition(int[] nums) {
int sum = 0;
for (int num : nums) {
sum += num;
}
// 和为奇数时，不可能划分成两个和相等的集合
if (sum % 2 != 0) return false;
int n = nums.length;
sum = sum / 2;
// dp[i][j] = x 定义：对于前 i 个物品，当前背包的容量为 j 时，若 x 为 true，则说明恰好能将背包装满，否则不能。
boolean[][] dp = new boolean[n + 1][sum + 1];
// base case
for (int i = 0; i <= n; i++) {
dp[i][0] = true;
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= sum; j++) {
if (j - nums[i - 1] < 0) {
// 背包容量不足，不能装入第 i 个物品
dp[i][j] = dp[i - 1][j];
} else {
// 装入或不装入背包
dp[i][j] = dp[i - 1][j] | dp[i - 1][j - nums[i - 1]];
}
}
}
return dp[n][sum];
}
值得注意的是，上面 dp[i][j] 都是通过上一行 dp[i-1][..] 转移过来的，因此可进行状态压缩如下：
/**
* 分割等和子集 -- 0-1 背包问题变种
* <p>
* 进行状态压缩，将二维dp数组压缩为一维，节约空间复杂度
*/
public boolean canPartition(int[] nums) {
int sum = 0, n = nums.length;
for (int num : nums) sum += num;
if (sum % 2 != 0) return false;
sum = sum / 2;
boolean[] dp = new boolean[sum + 1];
// base case
dp[0] = true;
for (int i = 0; i < n; i++) {
for (int j = sum; j >= 0; j--) {
if (j - nums[i] >= 0) {
dp[j] = dp[j] || dp[j - nums[i]];
}
}
}
return dp[sum];
}
上面值得注意的是，j 从后往前反向遍历，因为每个物品（或者说数字）只能用一次，以免之前的结果影响其他的结果。
时间复杂度 O(n*sum)，空间复杂度 O(sum)。
2. 最长子序列问题
2.1 最长递增子序列
最长递增子序列（Longes Increasing Subsequence，简写为 LIS）。
力扣 300 题如下：
动态规划的核心设计思想是 数学归纳法。
数学归纳法的思路如下：要证明一个数学结论，先假设这个结论在 k<n 时成立，然后根据这个假设，想办法推导证明 k=n 时此结论也成立。若能证明出来，就说明此结论对于 k 是任何数都成立。
类似的，设计动态规划算法，需要一个 dp 数组，先假设 dp[0...i-1] 都已经被算出来了，然后想办法通过这些结果算出 dp[i]。
对于最长递增子序列明确 dp 数组的定义：dp[i] 表示以 nums[i] 这个数结尾的最长递增子序列的长度。
根据这个定义，可以推出 base case：dp[i] 初始值为 1 (以 nums[i] 结尾的最长递增子序列起码要包含它自己)。最终结果是 dp 数组中的最大值。
代码实现如下：
/**
* 最长递增子序列
* <p>
* dp 数组的定义：dp[i] 表示以 nums[i] 这个数结尾的最长递增子序列的长度。
* <p>
* 时间复杂度：O(N^2)
*/
public int lengthOfLIS(int[] nums) {
int[] dp = new int[nums.length];
// base case: dp 数组初始化为 1
Arrays.fill(dp, 1);
for (int i = 0; i < nums.length; i++) {
for (int j = 0; j < i; j++) {
if (nums[i] > nums[j]) {
// 因为是递增子序列，只要找到前面那些结尾比 nums[i] 小的子序列，
// 然后把 nums[i] 接到最后，就可以形成一个新的递增子序列，而且这个新的子序列长度加一。
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
}
// 最终结果（子序列的最大长度）是 dp 数组中的最大值
int res = 0;
for (int len : dp) {
res = Math.max(res, len);
}
return res;
}
小结：
明确
dp数组所存数据的含义。根据
dp数组的定义，运用数学归纳法的思想，假设dp[0...i-1]都已知，想办法求出dp[i]。
当然上面这题也可以用二分查找法来解，时间复杂度更低为 O(NlogN)，如下：
/**
* 最长递增子序列 -- 二分查找
* <p>
* 时间复杂度： O(NlogN)
*/
public int lengthOfLis(int[] nums) {
int[] top = new int[nums.length];
// 牌堆数初始化为 0
int piles = 0;
for (int i = 0; i < nums.length; i++) {
// 要处理的扑克牌
int poker = nums[i];
// 搜索左侧边界的二分查找
int left = 0, right = piles;
while (left < right) {
int mid = (left + right) / 2;
if (top[mid] > poker) {
right = mid;
} else if (top[mid] < poker) {
left = mid + 1;
} else {
right = mid;
}
}
// 没找到合适的牌堆，新建一堆
if (left == piles) piles++;
// 把这张牌放到牌堆顶
top[left] = poker;
}
// 牌堆数就是 LIS 长度
return piles;
}
2.2 俄罗斯套娃信封问题
力扣 354 题如下：
这题其实是上面最长递增子序列的一个变种，每次合法的嵌套是大的套小的，相当于找一个最长递增的子序列，其长度就是最多能嵌套的信封个数。
解题思路：先对宽度 w 进行升序排序，如果遇到 w 相同的情况，则按照高度 h 降序排序。之后把所有的 h 作为一个数组，在这个数组上计算 LIS 的长度就是答案。
代码实现如下：
/**
* 俄罗斯套娃信封问题
*
* @param envelopes envelopes[i] = [wi, hi] ，表示第 i 个信封的宽度和高度
*/
public int maxEnvelopes(int[][] envelopes) {
int n = envelopes.length;
// 按宽度升序排列，若宽度一样则按高度降序排列
Arrays.sort(envelopes, new Comparator<int[]>() {
@Override
public int compare(int[] a, int[] b) {
return a[0] == b[0] ? b[1] - a[1] : a[0] - b[0];
}
});
// 对高度数组寻找 LIS
int[] height = new int[n];
for (int i = 0; i < n; i++) {
height[i] = envelopes[i][1];
}
return lengthOfLis(height);
}
/**
* 最长递增子序列
*/
private int lengthOfLis(int[] nums) {
int[] top = new int[nums.length];
int piles = 0;
for (int i = 0; i < nums.length; i++) {
int poker = nums[i];
int left = 0, right = piles;
while (left < right) {
int mid = (left + right) / 2;
if (top[mid] > poker) {
right = mid;
} else if (top[mid] < poker) {
left = mid + 1;
} else {
right = mid;
}
}
if (left == piles) piles++;
top[left] = poker;
}
return piles;
}
上面时间复杂度为 O(NlogN)，空间复杂度为 O(N)。
2.3 最长子序和
力扣 53 题如下：
滑动窗口算法是专门处理子串/子数组问题的，但这道题数组中的数字可以是负数（会有无法判断何时收缩窗口的情况），因而不能用滑动窗口算法。
这道题和上面的最长递增子序列很相似，定义 dp 数组如下：以 nums[i] 为结尾的「最大子数组和」为 dp[i]。
根据这个定义，最后遍历整个 dp 数组寻找最大值即可：
int res = Integer.MIN_VALUE;
for (int i = 0; i < n; i++) {
res = Math.max(res, dp[i]);
}
return res;
现假设已算出 dp[i-1]，那么 dp[i] 有两种「选择」，要么与前面的相邻子数组连接，形成一个和更大的子数组；要么不与前面的子数组连接，自成一派，自己作为一个子数组。如下：
// 要么自成一派，要么和前面的子数组合并
dp[i] = Math.max(nums[i], nums[i] + dp[i - 1]);
代码实现如下：
/**
* 最大子序和
* <p>
* dp 数组的定义：以nums[i]为结尾的「最大子数组和」为dp[i]
*/
public int maxSubArray(int[] nums) {
int n = nums.length;
if (n == 0) return 0;
int[] dp = new int[n];
// base case: 第一个元素前面没有子数组
dp[0] = nums[0];
// 状态转移方程
for (int i = 1; i < n; i++) {
dp[i] = Math.max(nums[i], nums[i] + dp[i - 1]);
}
// 得到 nums 的最大子数组
int res = Integer.MIN_VALUE;
for (int i = 0; i < n; i++) {
res = Math.max(res, dp[i]);
}
return res;
}
上面时间、空间复杂度都是 O(N)，注意到 dp[i] 仅仅和 dp[i-1] 的状态有关，还可以进一步状态压缩，把空间复杂度降低：
/**
* 最大子序和
*/
public int maxSubArray(int[] nums) {
int n = nums.length;
if (n == 0) return 0;
// base case:
int dp_0 = nums[0];
int dp_1 = 0, res = dp_0;
// 状态转移方程
for (int i = 1; i < n; i++) {
// dp[i] = Math.max(nums[i], nums[i] + dp[i - 1]);
dp_1 = Math.max(nums[i], nums[i] + dp_0);
dp_0 = dp_1;
// 顺便计算最大的结果
res = Math.max(res, dp_1);
}
return res;
}
小结：定义 dp 数组时要注意 dp[i-1]和 dp[i] 要建立起联系，再利用数学归纳法写出状态转移方程。
2.4 最长公共子序列
计算最长公共子序列（Longest Common Subsequence，简称 LCS）是一道经典的动态规划题目。
力扣 1143 题如下：
对于两个字符串求子序列的问题，都是用两个指针 i 和 j 分别在两个字符串上移动，大概率是动态规划思路。
首先，定义 dp 函数如下：dp(s1, i, s2, j) 计算 s1[i..] 和 s2[j..] 的最长公共子序列长度。
根据这个定义，最终答案就是 dp(s1, 0, s2, 0)，base case 就是 i == len(s1) 或 j == len(s2) 时：
int longestCommonSubsequence(String s1, String s2) {
return dp(s1, 0, s2, 0);
}
// 定义：计算 s1[i..] 和 s2[j..] 的最长公共子序列长度
int dp(String s1, int i, String s2, int j) {
// base case
if (i == s1.length() || j == s2.length()) {
return 0;
}
// ...
接着，实现 dp 函数：
/**
* 定义：dp(s1, i, s2, j)计算s1[i..]和s2[j..]的最长公共子序列长度。
*/
private int dp(String s1, int i, String s2, int j) {
// base case
if (i == s1.length() || j == s2.length()) {
return 0;
}
if (s1.charAt(i) == s2.charAt(j)) {
// s1[i] 和 s2[j] 必然在 lcs 中，
// 加上 s1[i+1..] 和 s2[j+1..] 中的 lcs 长度，就是答案
return 1 + dp(s1, i + 1, s2, j + 1);
} else {
// s1[i] 和 s2[j] 中至少有一个字符不在 lcs 中，
// 穷举三种情况的结果，取其中的最大结果
return max(
// 情况一、s1[i] 不在 lcs 中
dp(s1, i + 1, s2, j),
// 情况二、s2[j] 不在 lcs 中
dp(s1, i, s2, j + 1),
// 情况三、都不在 lcs 中(这种情况可忽略)
dp(s1, i + 1, s2, j + 1)
);
}
}
private int max(int a, int b, int c) {
return Math.max(a, Math.max(b, c));
}
以上便是暴力穷举法。
最后，用备忘录的方法消除重叠子问题，如下：
/**
* 最长公共子序列
*/
public int longestCommonSubsequence(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;
}
}
return dp(memo, s1, 0, s2, 0);
}
/**
* 定义：dp(s1, i, s2, j)计算s1[i..]和s2[j..]的最长公共子序列长度。
*/
private int dp(int[][] memo, String s1, int i, String s2, int j) {
// base case
if (i == s1.length() || j == s2.length()) {
return 0;
}
// 查找备忘录
if (memo[i][j] != -1) return memo[i][j];
if (s1.charAt(i) == s2.charAt(j)) {
// s1[i] 和 s2[j] 必然在 lcs 中，
memo[i][j] = 1 + dp(memo, s1, i + 1, s2, j + 1);
} else {
// s1[i] 和 s2[j] 中至少有一个字符不在 lcs 中，
memo[i][j] = Math.max(
dp(memo, s1, i + 1, s2, j),
dp(memo, s1, i, s2, j + 1)
);
}
return memo[i][j];
}
当然，也可以用 DP table 来解，如下：
/**
* 最长公共子序列 -- DP table
*/
public int longestCommonSubsequence2(String s1, String s2) {
int m = s1.length();
int n = s2.length();
// 定义：s1[0..i-1] 和 s2[0..j-1] 的 lcs 长度为 dp[i][j]
// 目标：s1[0..m-1] 和 s2[0..n-1] 的 lcs 长度，即 dp[m][n]
// base case: dp[0][..] = dp[..][0] = 0
int[][] dp = new int[m + 1][n + 1];
for(int i = 0; i < m; i++){
dp[i][0] = 0;
}
for(int j = 0; j < n; j++){
dp[0][j] = 0;
}
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
// s1[i-1] 和 s2[j-1] 必然在 lcs 中
dp[i][j] = 1 + dp[i - 1][j - 1];
} else {
// s1[i-1] 和 s2[j-1] 至少有一个不在 lcs 中
dp[i][j] = Math.max(dp[i][j - 1], dp[i - 1][j]);
}
}
}
return dp[m][n];
}
2.5 两个字符串的删除操作
力扣 583 题如下：
显然，上面的删除的结果就是它俩的最长公共子序列，因此容易推算出所需删除的次数：
/**
* 两个字符串的删除操作
*/
public int minDistance(String word1, String word2) {
int m = word1.length();
int n = word2.length();
// 最长公共子序列
int lcs = longestCommonSubsequence(word1, word2);
return m - lcs + n - lcs;
}
2.6 两个字符串的最小ASCII删除和
力扣 712 题如下：
这道题还是依照之前的思路，修改 base case 和状态转移部分即可直接写出解法代码：
/**
* 两个字符串的最小ASCII删除和
*/
public int minimumDeleteSum(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;
}
}
return dp2(memo, s1, 0, s2, 0);
}
/**
* 定义：将 s1[i..] 和 s2[j..] 删除成相同字符串，最小的 ASCII 码之和为 dp(s1, i, s2, j)。
*/
private int dp2(int[][] memo, String s1, int i, String s2, int j) {
int res = 0;
// base case
if (i == s1.length()) {
// 如果 s1 到头了，那么 s2 剩下的都得删除
for (; j < s2.length(); j++) {
res += s2.charAt(j);
}
return res;
}
if (j == s2.length()) {
// 如果 s2 到头了，那么 s1 剩下的都得删除
for (; i < s1.length(); i++) {
res += s1.charAt(i);
}
return res;
}
// 查找备忘录
if (memo[i][j] != -1) return memo[i][j];
// 添加备忘录
if (s1.charAt(i) == s2.charAt(j)) {
// s1[i] 和 s2[j] 都是在 lcs 中的，不用删除
memo[i][j] = dp2(memo, s1, i + 1, s2, j + 1);
} else {
// s1[i] 和 s2[j] 至少有一个不在 lcs 中，删一个
memo[i][j] = Math.min(
s1.charAt(i) + dp2(memo, s1, i + 1, s2, j),
s2.charAt(j) + dp2(memo, s1, i, s2, j + 1)
);
}
return memo[i][j];
}
2.7 最长回文子序列
力扣 516 题如下：
首先，定义一个 dp 函数：在子串 s[i..j] 中，最长回文子序列的长度为 dp[i][j]。
根据定义， 若只有一个字符，则最长回文子序列长度是 1，即 base case 就是 dp[i][j] = 1,(i == j)。而对于那些 i > j 的位置，不存在什么子序列，应初始化为 0。
接着，dp[i][j] 的值取决于 s[i] 和 s[j] 的字符，实现 dp 函数逻辑如下：
if (s[i] == s[j])
// 若相等，它俩一定在最长回文子序列中
dp[i][j] = dp[i + 1][j - 1] + 2;
else
// 若不等，s[i+1..j] 和 s[i..j-1] 谁的回文子序列更长？
dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);
最后，代码实现如下：
/**
* 最长回文子序列
*/
public int longestPalindromeSubseq(String s) {
int n = s.length();
// dp 数组定义： 在子串 s[i..j] 中，最长回文子序列的长度为 dp[i][j]
int[][] dp = new int[n][n];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
dp[i][j] = 0;
}
}
// base case
for (int i = 0; i < n; i++) {
dp[i][i] = 1;
}
// 反着遍历保证正确的状态转移
for (int i = n - 1; i >= 0; i--) {
for (int j = i + 1; j < n; j++) {
// 状态转移方程
if (s.charAt(i) == s.charAt(j)) {
dp[i][j] = dp[i + 1][j - 1] + 2;
} else {
dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);
}
}
}
// 整个 s 的最长回文子串长度
return dp[0][n - 1];
}
小结：
对于子序列问题，主要是 dp 数组的定义思路，不同的问题可能需要不同的 dp 数组定义来解决。
- 思路一：一个一维的 dp 数组
int n = array.length;
int[] dp = new int[n];
for (int i = 1; i < n; i++) {
for (int j = 0; j < i; j++) {
dp[i] = 最值(dp[i], dp[j] + ...)
}
}
比如最长递增子序列就是这种思路，dp 数组的含义如下：
在子数组 array[0..i] 中，以 array[i] 结尾的目标子序列（最长递增子序列）的长度是 dp[i]。
- 思路一：一个二维的 dp 数组
int n = arr.length;
int[][] dp = new dp[n][n];
for (int i = 0; i < n; i++) {
for (int j = 1; j < n; j++) {
if (arr[i] == arr[j])
dp[i][j] = dp[i][j] + ...
else
dp[i][j] = 最值(...)
}
}
这种思路运用相对多一些，尤其是涉及两个字符串/数组的子序列。本思路中 dp 数组含义又分为「只涉及一个字符串」和「涉及两个字符串」两种情况。
涉及两个字符串/数组时（比如最长公共子序列），dp 数组的含义如下：
在子数组 arr1[0..i] 和子数组 arr2[0..j] 中，我们要求的子序列（最长公共子序列）长度为 dp[i][j]。
只涉及一个字符串/数组时（比如最长回文子序列），dp 数组的含义如下：
在子数组 array[i..j] 中，我们要求的子序列（最长回文子序列）的长度为 dp[i][j]。
参考链接：
