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

题目链接：1049. 最后一块石头的重量 II

视频讲解：

动态规划之背包问题，这个背包最多能装多少？LeetCode：1049.最后一块石头的重量II_哔哩哔哩_bilibili

代码随想录 (programmercarl.com)

 看完代码随想录之后的想法：

这道题我们可以理解为，我们尽量把这堆石头分成两堆重量尽量相同的石头堆；

然后我们从这个数组中任意寻找石头，求得容量为数组值一般的石头堆的最大值

我们要知道动态规划的五部曲；

1，确定dp数组的含义，下标的含义；

2，确定递推公式；

3，确定dp数组如何初始化；

4，确定遍历顺序；

5，打印dp数组（用来debug）

dp[j] 是容量为j的石头堆最大的值为dp[j]；

因为这道题是0，1背包，我们用过了一个石头就不能使用了；

直接使用0，1背包的知识就可以了；

class Solution {
    public int lastStoneWeightII(int[] stones) {
        int[] dp = new int[1501];
        int sum = 0; 
        for(int n : stones)
            sum += n;
        int target = sum / 2;
        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 - 2 * dp[target];
    }
}

题目链接：494. 目标和 

文章讲解：代码随想录

视频讲解：动态规划之背包问题，装满背包有多少种方法？| LeetCode：494.目标和_哔哩哔哩_bilibili

看完代码随想录之后的想法：

这题是组合问题，挺难的；

class Solution {
    public int findTargetSumWays(int[] nums, int num) {
        int[] dp = new int[1001];
        dp[0] = 1;
        int sum = 0;
        for(int n : nums)
            sum += n;
        if(Math.abs(num) > sum) return 0;
        int target = (sum + num) / 2;
        if((sum + num) % 2 == 1) return 0;
        for(int i = 0; i < nums.length; i++) {
            for(int j = target; j >=nums[i]; j--)
                dp[j] += dp[j - nums[i]];
        }
        return dp[target];
    }
}

题目链接 474.一和零  

代码随想录