1049. 最后一块石头的重量 II
思路
求剩余石头的最小重量。如果两个石头最接近总重量的平均值，那么剩余石头为最小重量。
所以先求出石头的总重量的一半。
1.数组以及下标的含义
dp[j]表示容量为j的背包，最多可以装重量为j的石头
2.确定递推公式
dp[j] = max(dp[j], dp[j - stones[i]] + stones[i])
3.数组初始化
因为石头的1 <= stones.length <= 30，1 <= stones[i] <= 1000，所以总重量的一半为15000，开始时，重量为0，将所有的值都初始化为0
4.确定遍历顺序
先遍历石头，在遍历背包。
实现
点击查看代码
class Solution {
public:
int lastStoneWeightII(vector<int>& stones) {
vector<int> dp(15001,0);
int sum = 0;
for(int i = 0; i < stones.size(); i++) {
sum += stones[i];
}
int target = sum/2;
for(int i = 0; i < stones.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];
}
};
复杂度分析
- 时间复杂度：O(n×m)，n为石头的数量，m为总重量的一半。
- 空间复杂度：O(m)
494. 目标和
思路
既然为target，那么就一定有 left组合 - right组合 = target。
left + right等于sum，而sum是固定的。
所以left = (target + sum)/2 。
target是固定的，sum是固定的，left就可以求出来。
此时问题就是在集合nums中找出和为left的组合。
实现
点击查看代码
class Solution {
public:
int findTargetSumWays(vector<int>& nums, int target) {
int sum = 0;
for(int i = 0; i < nums.size(); i++) {
sum += nums[i];
}
if(abs(target) > sum) return 0;
if((sum + target) % 2 == 1) return 0;
int left = (sum + target) / 2;
vector<int> dp(left + 1);
dp[0] = 1;
for(int i = 0; i < nums.size(); i++) {
for(int j = left; j >= nums[i]; j--) {
dp[j] += dp[j - nums[i]];
}
}
return dp[left];
}
};
复杂度分析
- 时间复杂度：O(n×m)，m为背包数量
- 空间复杂度：O(m)
474. 一和零
思路
1.数组下标以及含义
dp[i][j]：最多有i个0和j个1的strs的最大子集的大小为dp[i][j]。
2.递推
dp[i][j] = max(dp[i][j], dp[i-num0][j-num1] + 1);
3.初始化
全部初始化为0
4.遍历顺序
为了不被覆盖，从后向前遍历
实现
点击查看代码
class Solution {
public:
int findMaxForm(vector<string>& strs, int m, int n) {
vector<vector<int>> dp(m+1,vector<int>(n+1, 0));
for(int a = 0; a < strs.size(); a++) {
vector<int> path = count(strs, a);
int num0 = path[0];
int num1 = path[1];
for(int i = m; i >= num0; i--) {
for(int j = n; j >= num1; j--) {
dp[i][j] = max(dp[i][j], dp[i - num0][j - num1] + 1);
//cout<< i << " " << j << " "<< dp[i][j] <<endl;
}
}
}
return dp[m][n];
}
vector<int> count(vector<string>& strs, int a) {
vector<int> result(2,0);
for(int i = 0; i < strs[a].size(); i++) {
if(strs[a][i] == '0') result[0]++;
else if(strs[a][i] == '1') result[1]++;
}
return result;
}
};
复杂度分析
- 时间复杂度：O(n×m×s)，s为数组的大小
- 空间复杂度：O(n×m)