动态规划章节理论基础:
https://programmercarl.com/%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%80.html
1049.最后一块石头的重量II
题目链接:https://leetcode.cn/problems/last-stone-weight-ii/
思路:
本题其实就是尽量让石头分成重量相同的两堆,相撞之后剩下的石头最小,这样就化解成01背包问题了,和昨天的416.分割等和子集 非常像。
本题物品的重量为stones[i],物品的价值也为stones[i]。对应着01背包里的物品重量weight[i]和 物品价值value[i]。
动规五部曲:
(1)确定dp数组以及下标含义
dp[j]表示容量(这里说容量更形象,其实就是重量)为j的背包,最多可以背最大重量为dp[j]。
(2)确定递归公式
01背包的递推公式为:dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
本题则是:dp[j] = max(dp[j], dp[j - stones[i]] + stones[i]);
(3)dp数组初始化
dp[j]中的j表示容量,那么最大容量(重量)是多少呢,就是所有石头的重量和。
可以把石头遍历一遍,计算出石头总重量 然后除2,得到dp数组的大小。
(4)确定遍历顺序
如果使用一维dp数组,物品遍历的for循环放在外层,遍历背包的for循环放在内层,且内层for循环倒序遍历。
(5)举例推导dp数组
举例,输入:[2,4,1,1],此时target = (2 + 4 + 1 + 1)/2 = 4 ,dp数组状态图如下:
最后dp[target]里是容量为target的背包所能背的最大重量。
那么分成两堆石头,一堆石头的总重量是dp[target],另一堆就是sum - dp[target]。
在计算target的时候,target = sum / 2 因为是向下取整,所以sum - dp[target] 一定是大于等于dp[target]的。
那么相撞之后剩下的最小石头重量就是 (sum - dp[target]) - dp[target]。
代码:
class Solution {
public int lastStoneWeightII(int[] stones) {
int sum = 0;
for(int i:stones)
sum += i;
// 把石头分成两堆
int target = sum >> 1;
int[] dp = new int[target+1];
for(int i = 0; i < stones.length; i++){
for(int j = target ; j>= stones[i] ;j--)
dp[j] = Math.max(dp[j],dp[j-stones[i]] + stones[i]);
}
// 一堆是dp[target] , 那么另一堆一定是sum - dp[target]
// 同时target是向下取整的,因此 sum - dp[target] 一定大于 dp[target]
return (sum-dp[target]) - dp[target];
}
}
494.目标和
题目链接:https://leetcode.cn/problems/target-sum/
思路:
这道题目咋眼一看和动态规划背包啥的也没啥关系。
本题要如何使表达式结果为target,
既然为target,那么就一定有 left组合 - right组合 = target。
left + right = sum,而sum是固定的。right = sum - left
公式来了, left - (sum - left) = target 推导出 left = (target + sum)/2 。
target是固定的,sum是固定的,left就可以求出来。
此时问题就是在集合nums中找出和为left的组合。(核心)
这里的left,就是bagSize,也就是我们后面要求的背包容量。
同时,看到(target + sum) / 2 应该担心计算的过程中向下取整有没有影响。
这么担心就对了,例如sum 是5,S是2的话其实就是无解的,所以:
if ((target + sum) % 2 == 1) return 0; // 此时没有方案
同时如果 target的绝对值已经大于sum,那么也是没有方案的。
if (abs(target ) > sum) return 0; // 此时没有方案
因为每个物品(题目中的1)只用一次,所以是一个01背包问题。这次和之前遇到的背包问题不一样了,之前都是求容量为j的背包,最多能装多少。
本题则是装满有几种方法。其实这就是一个组合问题了。
动规五部曲:
(1)确定dp数组以及下标含义
dp[j] 表示:填满j(包括j)这么大容积的包,有dp[j]种方法
(2)确定递归公式
只要搞到nums[i],凑成dp[j]就有dp[j - nums[i]] 种方法。
例如:dp[j],j 为5,
已经有一个1(nums[i]) 的话,有 dp[4]种方法 凑成 容量为5的背包。
已经有一个2(nums[i]) 的话,有 dp[3]种方法 凑成 容量为5的背包。
已经有一个3(nums[i]) 的话,有 dp[2]中方法 凑成 容量为5的背包
已经有一个4(nums[i]) 的话,有 dp[1]中方法 凑成 容量为5的背包
已经有一个5 (nums[i])的话,有 dp[0]中方法 凑成 容量为5的背包
那么凑整dp[5]有多少方法呢,也就是把 所有的 dp[j - nums[i]] 累加起来。
所以求组合类问题的公式,都是类似这种:
dp[j] += dp[j - nums[i]]
这个公式非常重要,会反复用到!
(3)dp数组初始化
从递推公式可以看出,在初始化的时候dp[0] 一定要初始化为1,因为dp[0]是在公式中一切递推结果的起源,如果dp[0]是0的话,递推结果将都是0。
所以本题我们应该初始化 dp[0] 为 1。
(4)确定遍历顺序
对于01背包问题一维dp的遍历,nums放在外循环,target在内循环,且内循环倒序。
(5)举例推导dp数组
输入:nums: [1, 1, 1, 1, 1], S: 3
bagSize = (S + sum) / 2 = (3 + 5) / 2 = 4
dp数组状态变化如下:
代码:
class Solution {
public int findTargetSumWays(int[] nums, int target) {
// left 代表所有取正数的元素 right 代表所有取负数的元素
// left - right = target && left + right = sum
// right + target = sum - right = left
// 2 * left = sum + target => left = (sum + target) /2
int sum = 0;
for(int i:nums)
sum += i;
if(Math.abs(target) > sum || (target + sum) % 2 != 0 ) return 0;
int left = (sum + target) >> 1;
// 本题的关键就在于在nums找出和为left的组合
int[] dp = new int[left+1];
// 如果不初始化的话,dp累加就会一直为0
dp[0] = 1;
for(int i=0; i<nums.length;i++){
for(int j=left;j>=nums[i];j--)
// dp[j] 代表数组中若干个元素组合成和为j的方案数
// 已经有一个1(nums[i]) 的话,有 dp[4]种方法凑成容量为5的背包。
// 同理 1 ~ 5
//dp[5] = dp[0] + ... + dp[5]
dp[j] = dp[j] + dp[j-nums[i]];
}
return dp[left];
}
}
474.一和零
题目链接:https://leetcode.cn/problems/ones-and-zeroes/description/
思路:
把总共的 0 和 1 的个数视为背包的容量,每一个字符串视为装进背包的物品。这道题就可以使用 0-1 背包问题的思路完成,这里的目标值是能放进背包的字符串的数量。
动规五部曲:
(1)确定dp数组以及下标含义
dp[i][j][k] 表示输入字符串在子区间 [0, i] 能够使用 j 个 0 和 k 个 1 的字符串的最大数量。
(2)确定递归公式
- dp[i-1][j][k] 不选择当前考虑的字符串,至少是这个数值
- dp[i-1][j-当前字符串使用0的个数][k-当前字符串使用1的个数] 选择当前考虑的字符串
(3)dp数组初始化
为了避免分类讨论,通常多设置一行。这里可以认为,第 00个字符串是空串。第 0 行默认初始化为 0。
(4)确定遍历顺序
常规遍历顺序
(5)举例推导dp数组
略
代码:
class Solution {
public int findMaxForm(String[] strs, int m, int n) {
int len = strs.length;
int[][][] dp = new int[len+1][m+1][n+1];
for(int i = 1; i<=len;i++){
// 计算0和1的数量
int zeroNum = 0, oneNum = 0;
for (char ch : strs[i-1].toCharArray()) {
if (ch == '0') {
zeroNum++;
} else {
oneNum++;
}
}
for(int j=0; j<= m; j++){
for(int k=0; k<=n ;k++){
// 先保存上一步结果
dp[i][j][k] = dp[i-1][j][k];
if(j>= zeroNum && k>= oneNum){
dp[i][j][k] = Math.max(dp[i-1][j][k],dp[i-1][j-zeroNum][k-oneNum]+1);
}
}
}
}
return dp[len][m][n];
}
}
思考优化空间,因为当前行只参考了上一行的值,因此可以使用「滚动数组」,也可以「从后向前赋值」。
class Solution {
public int findMaxForm(String[] strs, int m, int n) {
// 动规五部曲
// 1.确定dp含义
// dp[i][j] 最多有i个0 和 j个1的strs的最大子集的大小为dp[i][j]
// 2.确定递推公式
// dp[i][j]可以由前一个strs里的字符串推导出来,当前strs里的字符串有zeroNum个0,oneNum个1
// dp[i][j] = dp[i-zeroNum][j-oneNum]+1
int len = strs.length;
// int[][][] dp = new int[len+1][m+1][n+1];
int[][] dp = new int[m + 1][n + 1];
// 计算0和1的数量
for (String str : strs) {
int zeroNum = 0, oneNum = 0;
for (char ch : str.toCharArray()) {
if (ch == '0') {
zeroNum++;
} else {
oneNum++;
}
}
for (int i = m; i >= zeroNum; i--) {
for (int j = n; j >= oneNum; j--) {
dp[i][j] = Math.max(dp[i][j], dp[i - zeroNum][j - oneNum] + 1);
}
}
}
// for(int i = 1; i<=len;i++){
// // 计算0和1的数量
// int zeroNum = 0, oneNum = 0;
// for (char ch : strs[i-1].toCharArray()) {
// if (ch == '0') {
// zeroNum++;
// } else {
// oneNum++;
// }
// }
// for(int j=0; j<= m; j++){
// for(int k=0; k<=n ;k++){
// // 先保存上一步结果
// dp[i][j][k] = dp[i-1][j][k];
// if(j>= zeroNum && k>= oneNum){
// dp[i][j][k] = Math.max(dp[i-1][j][k],dp[i-1][j-zeroNum][k-oneNum]+1);
// }
// }
// }
// }
// return dp[len][m][n];
return dp[m][n];
}
}