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

1049. 最后一块石头的重量

题目：
有一堆石头，用整数数组 stones 表示。其中 stones[i] 表示第 i 块石头的重量。
每一回合，从中选出任意两块石头，然后将它们一起粉碎。假设石头的重量分别为 x 和 y，且 x <= y。那么粉碎的可能结果如下：
如果 x == y，那么两块石头都会被完全粉碎；
如果 x != y，那么重量为 x 的石头将会完全粉碎，而重量为 y 的石头新重量为 y-x。
最后，最多只会剩下一块 石头。返回此石头 最小的可能重量 。如果没有石头剩下，就返回 0。
题目链接： 1049. 最后一块石头的重量 II
解题思路： 求容量为总和一半的背包的总价值 用总和减去总价值为另一半石头的重量 两者差值即剩余重量
代码如下：

class Solution {
    public int lastStoneWeightII(int[] stones) {
        int sum = 0;
        for (int i : stones) {
            sum += i;
        }
        int target = sum >> 1;
        //初始化dp数组
        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 - 2 * dp[target];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

494. 目标和

题目：
给你一个非负整数数组 nums 和一个整数 target 。向数组中的每个整数前添加 ‘+’ 或 ‘-’ ，然后串联起所有整数，可以构造一个 表达式 ：例如，nums = [2, 1] ，可以在 2 之前添加 ‘+’ ，在 1 之前添加 ‘-’ ，然后串联起来得到表达式 “+2-1” 。返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。


题目链接：494. 目标和
解题思路：
既然为target，那么就一定有 left组合 - right组合 = target。

left + right = sum，而sum是固定的。right = sum - left

公式来了， left - (sum - left) = target 推导出 left = (target + sum)/2 。

target是固定的，sum是固定的，left就可以求出来。

此时问题就是在集合nums中找出和为left的组合有几个
递归五部曲：
二维dp数组

1.dp数组的含义
dp[i][j]：遍历到数组第i个数时， left为j时的能装满背包的方法总数
2.递推公式
当nums[i] > j时，这时候nums[i]一定不能取，所以是dp[i - 1][j]种方案数
nums[i] <= j时，num[i]可取可不取，因此方案数是dp[i - 1][j] (不取)+ dp[i - 1][j - nums[i]]（取）
因为要求方法数的总和，所以取与不取是加和的关系

1.dp数组的含义
dp[j] 表示：填满j（包括j）这么大容积的包，有dp[j]种方法
2.递推公式
dp[j]为不放nums[i] dp[j-nums[i]]为放 然后使用加法原理
dp[j]=dp[j]+dp[j-nums[i]]
代码如下

class Solution {
    public int findTargetSumWays(int[] nums, int target) {
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        int diff = sum +target;
        //如果不能被2 整除 则说明找不到合适的集合 因为left是整数
        if (diff < 0 || diff % 2 != 0) {
            return 0;
        }
        int[] dp = new int[diff/2+1];
        dp[0]=1;
        for(int i=0;i<nums.length;i++){
            for(int j=diff/2;j>=nums[i];j--){
                dp[j]=dp[j]+dp[j-nums[i]];
            }
        }
        return dp[diff/2];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

474.一和零

题目：
给你一个二进制字符串数组 strs 和两个整数 m 和 n 。
请你找出并返回 strs 的最大子集的长度，该子集中 最多 有 m 个 0 和 n 个 1 。
如果 x 的所有元素也是 y 的元素，集合 x 是集合 y 的 子集 。

![在这里插入图片描述](https://img-blog.csdnimg.cn/1327daa739914b188f90408e5a6401a5.png

题目链接： 474.一和零
解题思路：
//dp数组 有i个m j个n的最大子集是dp[i][j]
物品是每个字符串
如果放该字符串 dp[i][j]=dp[i-numi][j-numj]+1 如果不放 则dp[i][j]=dp[i][j]
具体代码如下：

class Solution {
    public int findMaxForm(String[] strs, int m, int n) {
        //dp[i][j]表示i个0和j个1时的最大子集
        int[][] dp = new int[m + 1][n + 1];
        int oneNum, zeroNum;
        for (String str : strs) {
            oneNum = 0;
            zeroNum = 0;
            for (char ch : str.toCharArray()) {
                if (ch == '0') {
                    zeroNum++;
                } else {
                    oneNum++;
                }
            }
            //倒序遍历
            for (int i = m; i >= zeroNum; i--) {
                for (int j = n; j >= oneNum; j--) {
                    dp[i][j] = Math.max(dp[i][j], dp[i - zeroNum][j - oneNum] + 1);
                }
            }
        }
        return dp[m][n];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25