408算法题leetcode--第37天
1049. 最后一块石头的重量 II
题目地址:1049. 最后一块石头的重量 II - 力扣(LeetCode)
题解思路:01背包
时间复杂度:O(n*m)
空间复杂度:O(m)
代码:
class Solution {
public:
int lastStoneWeightII(vector<int>& stones) {
// 01背包,容量和价值一样,即目标是最大化使用容量
// 如[abcd],抵消后可以为a+b+c-d,也可以是a+b-c-d,即一堆和-另一堆和的最小值
// 第一堆 = sum - dp[sum/2],第二堆 = dp[sum / 2]
// 接下来开始dp,转化为找dp[]的最大值
// dp[]: 容量为j的背包的最大值
// 转移:dp[j] = max(dp[j], dp[j - stones[i]] + stones[i])
// 初始化:dp[i] = 0
// 顺序:先种类,后重量
vector<int>dp(15001, 0);
int sum = 0;
for(auto i : stones) sum += i;
int target = sum / 2;
int size = stones.size();
for(int i = 0; i < size; i++){
for(int j = target; j >= stones[i]; j--){
dp[j] = max(dp[j], dp[j - stones[i]] + stones[i]);
}
}
return sum - dp[target] - dp[target];
}
};
416. 分割等和子集
题目地址:416. 分割等和子集 - 力扣(LeetCode)
题解思路:dp,01背包
时间复杂度:O(n^2)
空间复杂度:O(n)
代码:
class Solution {
public:
bool canPartition(vector<int>& nums) {
// 01背包,容量和价值一样,即目标是最大化使用容量
// dp[]:容量为j的背包的最大价值
// dp[i] = i,只要dp[sum / 2] = sum / 2就返回true
// 初始化:dp[0] = 0
// 顺序:种类,容量
vector<int>dp(10001, 0); // 200 * 100 / 2
int sum = 0;
for(auto i : nums) sum += i;
int size = nums.size();
for(int i = 0; i < size; i++){
for(int j = sum / 2; j >= nums[i]; j--){
dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);
}
}
return dp[sum / 2] * 2 == sum; // 可以前面提前判断,如果sum为奇数,返回false
}
};
原文地址:https://blog.csdn.net/weixin_58073817/article/details/143051396
免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!