力扣刷题1049. 最后一块石头的重量 II

1049. 最后一块石头的重量 II - 力扣（LeetCode）

这一道题是求石子相撞后最小的值，难的是如何把这道题转换为背包，可以把这一堆石子分为两堆，让这两堆的石子重量差值最小，即为每一堆的石子重量为所有石子重量之和除二，这时候就可以转换成背包问题，套用背包模版，然后第一堆的重量即为dp[m][n]，第二堆的重量为sum-dp[m][n]，那么这两堆的重量在向减，得到的即为最小的重量Math.abs(（sum -  dp[m][n]） - dp[m][n])

public int lastStoneWeightII(int[] nums) {
        int sum = 0;
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
        }
        // System.out.println(sum);
        int m = nums.length;
        int n = sum / 2;
        int[][] dp = new int[m + 1][n + 1];
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (nums[i - 1] > j) {
                    //如果放不下当前元素
                    dp[i][j] = dp[i - 1][j];
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - nums[i - 1]] + nums[i - 1]);
                }
                //System.out.print(dp[i][j] + " ");
            }
            // System.out.println();
        }
        return Math.abs(sum - 2 * dp[m][n]) ;
    }