图片来源于网络经典动态规划
- 背包问题
- 最长子序列问题
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 题如下:
两个字符串的最小ASCII删除和这道题还是依照之前的思路,修改 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]
。
参考链接:
网友评论