力扣爆刷第73天–动态规划
零、背包问题总纲:
背包问题:一维数组,dp[j] = Math.max(dp[j], dp[j-nums[i]] + nums[i])。
01背包遍历顺序:先物品后背包,物品正序,背包逆序。
如若背包正序则会出现同一个物品重复放入,如物品1重量为1,背包空间为1时放入了,背包空间为2时又放入了。
如果先背包后物品,为了避免重复放入背包依然是逆序,背包容量固定时,每种背包容量只能放入一个物品,即为最大的物品,小的物品都放不进来或者被覆盖了。
求组合数排列数:dp[j] += dp[j - nums[i]]
完全背包遍历顺序:物品背包没有先后顺序,物品背包都是正序。因为同一个物品不限量可以放入多次,在背包采用正序中。
完全背包求组合数,物品在外,背包在内。求排列数,背包在外,物品在内。
一、416. 分割等和子集
题目链接:https://leetcode.cn/problems/partition-equal-subset-sum/description/
思路:等和分割子集,就是计算出总和的一半,然后把所有元素往里面装看最大值是否能达到一半,能达到即可划分,这就转换成一个背包问题了。文章来源:https://www.toymoban.com/news/detail-828341.html
class Solution {
public boolean canPartition(int[] nums) {
int sum = 0;
for(int i = 0; i < nums.length; i++) {
sum += nums[i];
}
if(sum % 2 != 0) return false;
sum = sum / 2;
int[] dp = new int[sum+1];
for(int i = 0; i < nums.length; i++) {
for(int j = sum; j >= nums[i] ; j--) {
dp[j] = Math.max(dp[j], dp[j-nums[i]] + nums[i]);
}
}
return dp[sum] == sum;
}
}
二、1049. 最后一块石头的重量 II
题目链接:https://leetcode.cn/problems/last-stone-weight-ii/description/
思路:本题说石头之间两两抵消,求最后余数,其实就是把石头划分为两堆,然后计算差值,差值即为最后一块石头的重量,那么求一半和的背包问题,即可。文章来源地址https://www.toymoban.com/news/detail-828341.html
class Solution {
public int lastStoneWeightII(int[] stones) {
int sum = 0;
for(int i = 0; i < stones.length; i++) {
sum += stones[i];
}
int temp = sum / 2;
int[] dp = new int[temp + 1];
for(int i = 0; i < stones.length; i++) {
for(int j = temp; j >= stones[i]; j--) {
dp[j] = Math.max(dp[j], dp[j-stones[i]] + stones[i]);
}
}
return sum - 2*dp[temp];
}
}
到了这里,关于力扣爆刷第73天--动态规划的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!