LeetCode 1049 最后一块石头的重量 II
🟡中等
https://leetcode.cn/problems/last-stone-weight-ii/description/
逆天思路：将石头分为两堆，两堆之差就是最后的答案。
那么问题就转化为了背包问题，背包的最大容量是 sum/2 ，求最接近最大容量的值。
递归
class Solution {
public:
int add_pack(vector<int>& stones,int index,int cap){
if(cap==0) return 0;
if(index==stones.size()) return cap;
if(stones[index]>cap){
return add_pack(stones,index+1,cap);
}
return min(add_pack(stones,index+1,cap),add_pack(stones,index+1,cap-stones[index]));
}
int lastStoneWeightII(vector<int>& stones) {
int sum = accumulate(stones.begin(),stones.end(),0);
int target = sum/2;
int remain = add_pack(stones,0,target);
if(sum%2){
return 2*remain+1;
}else{
return 2*remain;
}
}
};
动态规划
这里是从cap里减，也可以改成从0开始累加，找到最接近target的值，最后直接返回 sum-2*返回值。
class Solution {
public:
int lastStoneWeightII(vector<int>& stones) {
int sum = accumulate(stones.begin(), stones.end(), 0);
int target = sum / 2;
int dp[stones.size() + 1][target + 1];
memset(dp, 0, sizeof dp);
for (int i = 0; i <= target; i++) {
dp[stones.size()][i] = i;
}
for (int i = 0; i <= stones.size() - 1; i++) {
dp[i][0] = 0;
}
for (int i = stones.size() - 1; i >= 0; i--) {
for (int j = 0; j <= target; j++) {
if (stones[i] > j) {
dp[i][j] = dp[i + 1][j];
} else {
dp[i][j] = min(dp[i + 1][j], dp[i + 1][j - stones[i]]);
}
}
}
// int remain = add_pack(stones,0,target);
int remain = dp[0][target];
if (sum % 2) {
return 2 * remain + 1;
} else {
return 2 * remain;
}
}
};
class Solution {
public:
int closest(vector<int>& stones, int index, int target, vector<vector<int>>& memo) {
if (index == stones.size()) return 0;
if (memo[index][target] != -1) return memo[index][target];
// Don't take the current stone
int withoutCurrent = closest(stones, index + 1, target, memo);
// Take the current stone, if it doesn't exceed the target
int withCurrent = 0;
if (stones[index] <= target) {
withCurrent = stones[index] + closest(stones, index + 1, target - stones[index], memo);
}
memo[index][target] = max(withoutCurrent, withCurrent);
return memo[index][target];
}
int lastStoneWeightII(vector<int>& stones) {
int sum = accumulate(stones.begin(), stones.end(), 0);
int target = sum / 2;
vector<vector<int>> memo(stones.size(), vector<int>(target + 1, -1));
int closestWeight = closest(stones, 0, target, memo);
return sum - 2 * closestWeight;
}
};