🌕 1049. 最后一块石头的重量 II

难度: 🌕

• 问题描述
• 解法
• 输出

问题描述

---

解法

class Solution {
    public int lastStoneWeightII(int[] stones) {
        // 思路：
        // 背包问题，求能得到最大价值一般的能得到的最大价值，分为一组
        int sum = 0;
        for(int i : stones) {
            sum += i;
        }
        int res = sum;
        sum >>= 1;
        // 填充背包，使得价值尽可能接近最大价值的一半
        int len = stones.length;
        int[] dp = new int[sum + 1];
        for(int j = 0; j < len; j ++) {
            for(int i = sum; i - stones[j] >= 0; i --) {
                dp[i] = Math.max(dp[i], dp[i - stones[j]] + stones[j]);
            }
        }
        return Math.abs(2 * dp[sum] - res);
    }
}

---

输出