1049. 最后一块石头的重量 II
这道题仅仅是理解了。还有问题没想明白：
- 为什么求总和的平均值就可以了？不会出现两边石头数量不对等，导致碰撞后的情况不是sum-dp[target]*2的情况吗？
- dp的大小设成15000就可以，还是一定要150001？因为我跑15000的时候，也没有报错
class Solution { public: int lastStoneWeightII(vector<int>& stones) { vector<int> dp(15000,0); int sum = accumulate(stones.begin(),stones.end(),0); int target = sum/2; int total_size = stones.size(); for(int i=0; i<total_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]*2; } };
494. 目标和
看了评论里的一个提示，想到了这道题原来可以用回溯法做出来。虽然写的超时了，但是意思是对的。我写的超时了是因为我加了for loop，但其实有index+1的话，就不需要for loop了。因为这道题是要所有的数都带上，如果我写for loop的话，那势必会从第二位数再开始计算。但这对于本题没必要的。也说明了我不会根据题变通，回溯有背题的成分，而不是理解了。
class Solution {
public:
int result = 0;
void backtracking(vector<int>& nums, int sum,int index,int target){
if(index == nums.size()){
if(sum == target){
result++;
}
return ;
}
else{
backtracking(nums,sum+nums[index],index+1,target);
backtracking(nums,sum-nums[index],index+1,target);
}
}
int findTargetSumWays(vector<int>& nums, int target) {
backtracking(nums,0,0,target);
return result;
}
};
474.一和零
这道题看了几遍题解都没看懂。放弃了
