// @Title: 最后一块石头的重量 II (Last Stone Weight II)
// @Author: qisiii
// @Date: 2024-09-25 17:52:24
// @Runtime: 3 ms
// @Memory: 40.6 MB
// @comment: 
// @flag: 
class Solution {
    /**
     *其思想还是将石头分为两堆，计算在sum/2的容量下能取到的最大的可能的石头，最后sum-堆容量是另一堆，另一堆-当前堆是结果
     */
    public int lastStoneWeightII(int[] stones) {
        int sum=0;
        for(int i:stones){
            sum+=i;
        }   
        int target=sum/2;
        int[][] dp=new int[stones.length][target+1];
        for(int j=stones[0];j<=target;j++){
            dp[0][j]=stones[0];
        }
        for(int i=1;i<stones.length;i++){
            for(int j=1;j<=target;j++){
                if(j<stones[i]){
                    dp[i][j]=dp[i-1][j];
                }else{
                    dp[i][j]=Math.max(dp[i-1][j],dp[i-1][j-stones[i]]+stones[i]);
                }
            }
        }
        return sum-dp[stones.length-1][target]*2;
    }
}