Leetcode 1049. 最后一块石头的重量 II（DAY 80） ---- 动态规划学习期（现在才看到这道题原来一直没做出来）

原题题目

代码实现（二刷自解 首刷未解出来 C++）

class Solution {
    
public:int lastStoneWeightII(vector<int>& stones) {
    int sum = 0,size = stones.size(),ret;for(int i=0;i<size;++i)sum += stones[i];vector<int> dp1(2*sum+1,0),dp2(dp1),zerovec(dp1);dp2[sum] = 1;for(int temp = 0;temp<size;++temp){
    dp1 = dp2;dp2 = zerovec;for(int i = 2*sum;i>=0;--i)if(dp1[i])  dp2[i+stones[temp]] = dp2[i-stones[temp]] = 1;}for(int i=sum;i<=2*sum;++i){
    if(dp2[i]){
    ret = i - sum;break;}}return ret;}
};