代码随想录算法训练营第四十二天| 1049. 最后一块石头的重量 II、 494. 目标和

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

题目链接：https://leetcode.cn/problems/last-stone-weight-ii/description/
文章链接：https://programmercarl.com/1049.%E6%9C%80%E5%90%8E%E4%B8%80%E5%9D%97%E7%9F%B3%E5%A4%B4%E7%9A%84%E9%87%8D%E9%87%8FII.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE

思路

 * 最后一块石头的重量：将石头尽量平均分成两堆，即sum/2
 * 此时就可以计算出装满重量为sum/2的背包最大价值是多少
 * 那么这个最大价值就是一堆石头的重量，那么另一堆就是sum-最大价值
 * 两堆石头的重量之差就是最后剩余石头的最小重量

 public static int lastStoneWeightII(int[] stones) {
        int sum = Arrays.stream(stones).sum();
        int target = sum / 2;
        int[] dp = new int[target + 1];
        for (int i = 0; i < stones.length; i++) {
            for (int j = target; j > stones[i]; j--) {
                dp[j] = Math.max(dp[j], dp[j - stones[i]] + stones[i]);
            }
        }
        return (sum - dp[target]) - dp[target];
    }

LeetCode 494. 目标和

题目链接：https://leetcode.cn/problems/target-sum/description/
文章链接：https://programmercarl.com/0494.%E7%9B%AE%E6%A0%87%E5%92%8C.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE

思路

 * 目标和：若sum为总和，既然为target，那么就一定有 left组合 - right组合 = target
 * left + right = sum，而sum是固定的。right = sum - left
 * 公式来了， left - (sum - left) = target 推导出 left = (target + sum)/2
 * 那么问题转为装满容量为(target + sum)/2有几种装法
 * dp[j]表示装满背包容量为j的背包有多少种装法，那么对于第i个数，如果不装那依然是dp[j]种装法
 * 如果装，那就是dp[j-nums[i]]种装法，因此dp[j] = dp[j] + dp[j-nums[i]]

  public int findTargetSumWays(int[] nums, int target) {
        int sum = Arrays.stream(nums).sum();
        if (Math.abs(target) > sum)
            return 0;
        if ((target + sum) % 2 == 1)
            return 0;
        int bagSize = (target + sum) / 2;
        int[] dp = new int[bagSize + 1];
        dp[0] = 1;
        for (int i = 0; i < nums.length; i++) {
            for (int j = bagSize; j >= nums[i] ; j--) {
                dp[j] = dp[j] + dp[j-nums[i]];
            }
        }
        return dp[bagSize];
    }