LeetCode 1049. 最后一块石头的重量 II（DP）

示例：
输入：[2,7,4,1,8,1]
输出：1
解释：
组合 2 和 4，得到 2，所以数组转化为 [2,7,1,8,1]，
组合 7 和 8，得到 1，所以数组转化为 [2,1,1,1]，
组合 2 和 1，得到 1，所以数组转化为 [1,1,1]，
组合 1 和 1，得到 0，所以数组转化为 [1]，这就是最优值。
 
提示：
1 <= stones.length <= 30
1 <= stones[i] <= 1000

class Solution {	//C++
public:
    int lastStoneWeightII(vector<int>& stones) {
    	int i, j, n = stones.size(), sum = accumulate(stones.begin(),stones.end(), 0);
    	vector<vector<bool>> dp(n+1,vector<bool>(sum/2+1, false));
    	dp[0][0] = true;//dp[i][w], 遍历完第i个石头，可以得到重量为w吗？
    	for(i = 1; i <= n; i++)//样本维度
    	{
    		for(j = 0; j <= sum/2; ++j)//重量维度
    		{
    			if(dp[i-1][j])
    			{
    				dp[i][j] = dp[i-1][j];//不取
    				if(j+stones[i-1] <= sum/2)//不超，取
    					dp[i][j+stones[i-1]] = true;
    			}
    		}
    	}
    	j = sum/2;
    	while(dp[n][j] != true)//最接近一半的重量是 j 
    		j--;
    	return sum-2*j;//一半是sum-j，一半是 j,做差
    }
};

class Solution {	//C++
public:
    int lastStoneWeightII(vector<int>& stones) {
    	int i, j, n = stones.size(), sum = accumulate(stones.begin(),stones.end(), 0);
    	vector<bool> dp(sum/2+1, false);
    	dp[0] = true;//dp[w], 遍历完第i个石头，可以得到的重量为w吗？
    	for(i = 1; i <= n; i++)//样本维度
    	{
    		for(j = sum/2; j >= 0; --j)//重量维度
    		{
    			if(dp[j] && j+stones[i-1] <= sum/2)
    				dp[j+stones[i-1]] = true;
    		}
    	}
    	j = sum/2;
    	while(dp[j] != true)
    		j--;
    	return sum-2*j;
    }
};

class Solution:# py3
    def lastStoneWeightII(self, stones: List[int]) -> int:
        n = len(stones)
        s = sum(stones)
        dp = [False]*(s//2+1)
        dp[0] = True
        for i in range(1,n+1):
            for j in range(s//2,-1,-1):
                if dp[j] and j+stones[i-1] <= s//2:
                    dp[j+stones[i-1]] = True
        j = s//2
        while not dp[j]:
            j -= 1
        return s-2*j