摘要
- 用动态规划解决问题时,不仅要从简单的子问题来考虑递推公式,也要从问题的整体来考虑,看问题的输入参数本身有什么性质和公式,也有助于得到递推公式。
LeetCode1049 最后一块石头的重量 II
- 从问题的整体来考虑,要使一堆石头两两一起“粉碎”后剩余的重量值最小,那么应该把这堆石头尽可能地分成重量相等或相近的两堆石头,分出来的两堆石头两两一起“粉碎”后剩余的重量值就是最小的重量值。注意,如果粉碎后的石头有剩余,那可以看作继续分成重量尽可能相近的两堆,然后继续让这两堆石头两两一起粉碎。
- 将一堆石头分成两堆重量尽可能相近的石头,设石头的重量总和为
sum
- 对于石头
i
,要么在第一堆里,要么在第二堆里。只针对分出来的第一堆石头,石头i
要么在第一堆里,要么不在,这和 0-1 背包问题对于物品的取法是一致的。 - 两堆石头的重量要尽可能相近,所以分出来的一堆石头的重量最大值应该是
sum / 2 + sum % 2
。
- 对于石头
- 那么,问题可以转化成:“从一堆石头中任取石头,每个石头要么不取,要么取一次,得到的重量值尽可能地接近
sum / 2 + sum % 2
”。“物品”是石头,“背包”是一堆石头,“背包”的最大容量是sum / 2 + sum % 2
,“物品”的价值是stones[i]
,“物品”的重量也是stones[i]
。设half
为sum / 2 + sum % 2
。 -
dp
数组及下标的含义:dp[j]
表示的是,任取石头,得到的重量值不超过j
的最大值,设dp[j]
的更新次数为i
,则dp[j]
对应的可选的石头下标范围为0
到i
。 - 计算完
dp
数组后,按上述规则取石头后第一堆的重量为dp[half]
,第二堆的重量为sum - dp[half]
,则粉碎后剩余的重量为abs(sum - dp[half] - dp[half])
。
题解代码如下
class Solution {
public:
int lastStoneWeightII(vector<int>& stones) {
if (stones.empty()) return 0;
if (stones.size() == 1) return stones.back();
int sum = 0;
for (auto& iter : stones) sum += iter;
int half = sum / 2 + sum % 2;
vector<int> dp(half + 1, 0);
for (int i = 0; i < stones.size(); i++) {
for (int j = half; j >= stones[i]; j--) {
dp[j] = max(dp[j], dp[j - stones[i]] + stones[i]);
}
}
return abs(sum - dp[half] - dp[half]);
}
};
LeetCode494 目标和
- 这道题目,从整体来看,“构造表达式”也可以看作将输入的参数分为两部分:一部分添加
+
号,作为被减数;另一部分添加-
号,作为减数。设nums
中各个整数的和为sum
。设被减数为minuend
(正数),减数为subtractor
(正数),则两者的和为sum
,两者的差为target
。
通过以上推导,可以看出
minuend
的取法,即从nums
中任取k
个元素,使得选取的元素的和尽可能接近(sum+target)/2
,当选取的元素的和恰好等于(sum+target)/2
时,说明找到了一种使得构造的表达式的结果等于target
的方案。确定
dp
数组及下标的含义:dp[j]
为从nums
中任取整数,选取的整数的和恰好为j
的情况,dp[j]
的更新次数对应可以选取的nums
的下标范围,设dp[j]
更新了i
次,dp[j]
对应的可选取的nums
的下标范围是0
到i
。-
要注意的是,这道题目的
dp
数组的含义和之前的题目不同。- LeetCode1049 最后一块石头的重量、LeetCode416 分割等和子集,这两道题我们并不关心有多少种组合方式得到目标值,我们关心的是是否能得到目标值,或得到一个接近目标值的值。用 0-1 背包的语言来描述,就是想让背包尽可能地装满,或者装入的物品价值尽可能大。
- 但 LeetCode494 目标和,除了要关心是否能得到目标值,还要知道有多少种方法得到目标值。用 0-1 背包的语言来描述,就是有多少种方法恰好能装满背包。此时再用描述背包装入的重量或价值的
dp
来解决题目就不合适了,dp
数组应该描述的是有多少种方式能恰好装满容量为j
的背包。
-
确定递推公式,先看简单的子问题
- 一个元素都没有选取,选取出的
minuend
是空集,空集只有一种,且和为0
,所以dp[0]
初始化为1
,此时minuend
中整数的和只能是0
,所以当j > 0
时,dp[j]
初始化为0
。 -
nums[0]
是第一个尝试选取的元素,如果选nums[0]
,则当j == nums[0]
时,dp[j]
的值为1
,说明得到和为nums[0]
有一种方式,就是选取nums[0]
。 - 假设已经在
nums[0]
到nums[i-1]
中选取了k
个数,再选取了一个整数nums[i]
。那么为了使得当前选取方式的minuend
中的整数的和为j
,就要再从nums[0]
到nums[i-1]
选出一个和为j - nums[i]
的集合。根据dp
数组的定义,从nums[0]
到nums[i-1]
选出一个和为j - nums[i]
的集合的种数就是dp[j - nums[i]]
。 - 这样就可以得到递推公式,其中
i
为dp[j]
的更新次数下标(从0开始),i=-1
表示初始状态
- 一个元素都没有选取,选取出的
初始状态已经在递推公式中写明,即
dp[0]
初始化为1
,其他dp[j]
初始化为0
。-
以
nums={1, 1, 1, 1, 1}; target=3
为例,根据,求得minuend=4
,要注意的是,有两种情况是可以直接知道答案的种数是0
的:-
sum
的绝对值小于target
的绝对值,即abs(sum) < abs(target)
,此时说明nums
中的元素全取+
或全取-
都不可能得到值为target
的和。 -
sum + target
不能被2
整除,因为nums
中都是整数,对于minuend
的定义是从nums
中取出的部分整数的和,所以minuend
也应该是整数,如果sum + target
不能被2
整除,说明不存在minuend
使得构造出的表达式的结果为target
。
-
首先画出其二维
dp
数组,初始状态保存在i=-1
那一行,对应没有从nums
中选取任何整数
- 确定
dp[j]
的遍历顺序,即更新顺序,由递推公式 ,可以知道dp[j]
的更新依赖的是上一行的且在其左边的值,所以更新顺序应该是j
从大到小,即从左到右。 - 所以先滑动
dp[4]
,dp[4]=dp[4]+dp[4-1]=0;
-
dp[2]
和dp[3]
同理
- 再看
dp[1]
,nums[0]==1
,dp[1]=dp[1]+dp[1-1]=1
。
- 最后看
dp[0]
,如果j - nums[i] > 0
,则dp[0]
还是1
,因为没有出现空集以外的集合内元素和等于0
的情况。
- 重复滑动一行的过程,把
dp
数组填完
- 最后的
dp[minuend]
就是使得构造出的表达式的结果等于target
的方法数。
题解代码如下
class Solution {
public:
int findTargetSumWays(vector<int>& nums, int target) {
int sum = 0;
for (auto& iter : nums) sum += iter;
// 直接求得方法数为 0 的情况
if ((sum + target) % 2) return 0;
if (abs(sum) < abs(target)) return 0;
// 初始化 dp 数组
int minuend = (sum + target) / 2;
vector<int> dp(minuend + 1, 0);
dp[0] = 1;
// 从 i=0 开始,逐行更新 dp 数组
for (int i = 0; i < nums.size(); i++) {
for (int j = minuend; j >= nums[i]; j--) {
dp[j] += dp[j - nums[i]];
}
}
return dp[minuend];
}
};
LeetCode474 一和零
这道题目也是 0-1 背包问题,“物品”是集合中的元素,“背包”是子集。不过“物品”的“重量”变成了两个维度:一是“0”的个数,二是“1”的个数。题目要求子集中的元素个数最多,所以每个元素的“价值”是相等的,可以都设为
1
。确定
dp
数组及数组下标的含义:dp[j][k]
的含义是,从strs
中任取字符串,这些字符串包含的 '0' 不超过j
个,包含的 ’1‘ 不超过k
个。对每个物品,dp[j][k]
的值都会进行一次更新,所以依然可以省略遍历到第i
个物品这个维度。递推公式,可以看出只是“重量”多了一个维度,
dp[i][j][k]
还是由两种可能推出:一是不放入物品i
,二是放入物品i
初始化过程隐含在
dp
数组的计算过程中,先将dp
数组全部初始化成0
。同样要注意
dp[j][k]
的更新依赖于dp[j - numsOf0[i]][k - numsOf1[i]]
,所以j
应从大到小,k
也应该从大到小。
题解代码如下
class Solution {
public:
int findMaxForm(vector<string>& strs, int m, int n) {
vector<int> numsOf0(strs.size(), 0);
vector<int> numsOf1(strs.size(), 0);
for (int i = 0; i < strs.size(); i++) {
for (auto& ch : strs[i]) {
numsOf0[i] += ch == '0';
numsOf1[i] += ch == '1';
}
}
vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
for (int i = 0; i < strs.size(); i++) {
for (int j = m; j >= numsOf0[i]; j--) {
for (int k = n; k >= numsOf1[i]; k--) {
dp[j][k] = max(dp[j][k], dp[j - numsOf0[i]][k - numsOf1[i]] + 1);
}
}
}
return dp[m][n];
}
};