416 分割等和子集

题目：

题目难易：中等

给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

注意: 每个数组中的元素不会超过 100 数组的大小不会超过 200

示例 1:

  • 输入: [1, 5, 11, 5]
  • 输出: true
  • 解释: 数组可以分割成 [1, 5, 5] 和 [11].

示例 2:

  • 输入: [1, 2, 3, 5]
  • 输出: false
  • 解释: 数组不能分割成两个元素和相等的子集.

提示：

  • 1 <= nums.length <= 200
  • 1 <= nums[i] <= 100

思路：

题目中要求 ：使得两个子集的元素和相等。 那么就可以对数组中的所有元素求和， 如果sum%2 != 0 ,那么就直接返回false 。原因这里就不多了， 奇数怎么可能有两个相等的子集和呢?

如此一来就可以将本体转换为求数组中的元素之和能否等于 sum/2了。 这样就可以用到动态规划的思路来进行解题了。

dp[i] 表示 背包容量为 i 的背包， 所能容纳的物体的最大价值是 dp[i]

这里我们将数组中元素得到的最大子集和 抽象成为背包的最大价值 。

最后通过比较 dp[target] == target 来返回最后的结果即可。

推导公式 可以通过dp[j] = Math.max(dp[j], dp[j - weight[i]] + values[i])(**放与不放的状态取最大值)**得出 ，因为这里获取的是数字， 所以他的weight 和 value都是nums[i] 。按照上述的推导公式就可以得出。

实现

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
26
27
28
29
class Solution {
    public boolean canPartition(int[] nums) {
        //只需要找到每个数组中为sum/2的 ，如果出现sum为奇数，那么就返回false
        int sum = 0;
        for(int i =0 ;i <nums.length;i++){
            sum += nums[i];
        }
        if(sum % 2 != 0){
            return false;
        }
        //找到累加结果为target即可
        int target = sum /2 ;
        
        //dp[i]数组的含义是:容量为i 的背包 ，所能容纳的物品的最大价值为dp[i] 
        //换算到本题就是 容量为i的背包， 所能累加的数字的最大和为dp[i] 最后如果dp[target] == target 那么就返回true else false  
        int []dp = new int[target+1];
        //先遍历每一个数字
        for(int i =0; i < nums.length; i++){
            for(int j = target; j >= nums[i] ;j--){
                dp[j] = Math.max(dp[j] , dp[j-nums[i]] + nums[i]);
                // System.out.println("dp["+j+"]的结果是= "+dp[j]);
            }
        }

    
        return target == dp[target];
    }

}

1049 最后一块石头的重量

题目：

题目难度：中等

有一堆石头，每块石头的重量都是正整数。

每一回合，从中选出任意两块石头，然后将它们一起粉碎。假设石头的重量分别为 x 和 y，且 x <= y。那么粉碎的可能结果如下：

如果 x == y，那么两块石头都会被完全粉碎；

如果 x != y，那么重量为 x 的石头将会完全粉碎，而重量为 y 的石头新重量为 y-x。

最后，最多只会剩下一块石头。返回此石头最小的可能重量。如果没有石头剩下，就返回 0。

示例：

  • 输入：[2,7,4,1,8,1]
  • 输出：1

解释：

  • 组合 2 和 4，得到 2，所以数组转化为 [2,7,1,8,1]，
  • 组合 7 和 8，得到 1，所以数组转化为 [2,1,1,1]，
  • 组合 2 和 1，得到 1，所以数组转化为 [1,1,1]，
  • 组合 1 和 1，得到 0，所以数组转化为 [1]，这就是最优值。

提示：

  • 1 <= stones.length <= 30
  • 1 <= stones[i] <= 1000

实现

本题和上道题是一摸一样的套路， 仅仅是最后取得结果不同， 这需要知道最后还剩的最小 ，那么就是使用sum - dp[target] - dp[target]从而得到。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int lastStoneWeightII(int[] stones) {
        int sum = 0 ;
        for(int i= 0 ;i<stones.length;i++){
            sum += stones[i];
        }
        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];
    }

}

494 目标和

题目：

难度：中等

给定一个非负整数数组，a1, a2, …, an, 和一个目标数，S。现在你有两个符号 + 和 -。对于数组中的任意一个整数，你都可以从 + 或 -中选择一个符号添加在前面。

返回可以使最终数组和为目标数 S 的所有添加符号的方法数。

示例：

  • 输入：nums: [1, 1, 1, 1, 1], S: 3
  • 输出：5

解释：

  • -1+1+1+1+1 = 3
  • +1-1+1+1+1 = 3
  • +1+1-1+1+1 = 3
  • +1+1+1-1+1 = 3
  • +1+1+1+1-1 = 3

一共有5种方法让最终目标和为3。

提示：

  • 数组非空，且长度不会超过 20 。
  • 初始的数组的和不会超过 1000 。
  • 保证返回的最终结果能被 32 位整数存下
  • 提示：
    • 1 <= nums.length <= 20
    • 0 <= nums[i] <= 1000
    • 0 <= sum(nums[i]) <= 1000
    • -1000 <= target <= 1000

思路 ：

二刷才理解这道题的做法，所以本次刷题的时候还是没做出来。 因为单纯的从题目本身是无法联想到怎么应用到动态规划的。

从题目中看， 也就是一个两位数相减的问题， 加号我们这里省略， 所以 就可以通过 left - right == target left 是这个数组的一部分内容相加得到； 同理 right 是数组的另一部分相加得到 。然后就可以看出 目标数就是两个数组子集和 相减得到的。 同时，这两个数 相加的结果一定是整个数组的sum 。因此就可以得到left + right == sum sum是固定的。

从上述的两个式子中，我们可以得到left = (sum + target) /2 。突然间， 问题就回归到了 数组中的内容求和 等于 left 有几种方法了。 这样就可以联系到动态规划的思路了 。

dp[i]表示 内容求和为 i 的方法有 dp[i]种 .

按照思路就可以得到递推公式 dp[j] += dp[j - nums[i]]。

注意：这里需要排除target < 0 && sum + target < 0 的情况， 因为数组中的每个数都是大于 0 的如果sum + target < 0 那么就说明target 是小于 -sum的 。所以是不存在的。

实现

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
26
class Solution {
        //可以将本题看成两个数相减， left - right = target 
        //因为两个数的 left + right = sum 这个sum是固定的 那么就可以通过这两个式子推导出 
        //left = ( sum + target ) /2
        //所以本题就变成了求和为left的种类数了  
    public int findTargetSumWays(int[] nums, int target) {
        //dp数组的含义: 向背包容量为 i 的背包中添加nums[i] 的物品， 背包的最大价值是dp[i]
        //这里的最大价值就是表达式的种类数
        int sum = 0; 
        for(int i =0 ;i < nums.length;i++){
            sum += nums[i];
        }
        if ( target < 0 && sum < -target) return 0;
        if((sum + target)%2 != 0 ) return 0;
        int left = (sum + target) / 2 ;
        int []dp = new int[left + 1];
        dp[0] = 1;
        
        for(int i =0 ; i< nums.length ; i++){
            for(int j= left; j >= nums[i];j--){
                dp[j] += dp[j - nums[i]];
            }
        }
        return dp[left];
    }
}

474 一和零

题目：

给你一个二进制字符串数组 strs 和两个整数 m 和 n 。

请你找出并返回 strs 的最大子集的大小，该子集中 最多 有 m 个 0 和 n 个 1 。

如果 x 的所有元素也是 y 的元素，集合 x 是集合 y 的 子集 。

示例 1：

  • 输入：strs = [“10”, “0001”, “111001”, “1”, “0”], m = 5, n = 3
  • 输出：4
  • 解释：最多有 5 个 0 和 3 个 1 的最大子集是 {“10”,”0001”,”1”,”0”} ，因此答案是 4 。 其他满足题意但较小的子集包括 {“0001”,”1”} 和 {“10”,”1”,”0”} 。{“111001”} 不满足题意，因为它含 4 个 1 ，大于 n 的值 3 。

示例 2：

  • 输入：strs = [“10”, “0”, “1”], m = 1, n = 1
  • 输出：2
  • 解释：最大的子集是 {“0”, “1”} ，所以答案是 2 。

提示：

  • 1 <= strs.length <= 600
  • 1 <= strs[i].length <= 100
  • strs[i] 仅由 ‘0’ 和 ‘1’ 组成
  • 1 <= m, n <= 100

思路

和上道题一样， 这道题还是2刷都未做出来 ，还是刚开始的固有思维没有发散到通过其他方法来转换到动态规划， 所以导致题目一转换就忘了怎么出发。

strs 的最大子集的大小，该子集中 最多 有 m 个 0 和 n 个 1 。 用滚动数组(一维数组)的方法是很难想出来的，还是需要使用二维数组 ，因为这里的变量有两个， 所以需要滚动二维数组(自创词) 来解决。

dp[i][j] : 就可以表示为 有 i个 0 和 j 个 1 组成的最大子集的大小是dp[i][j]

但是这里子集的 0 和 1 都不好确定， 我这边使用的是一种笨办法 ，通过两个数组（zeroNum and oneNum）来记录 strs 中每个元素中的 0 和 1 的个数

这样我们在遍历的时候就可以直接拿来用了。（其实还有更好的）

求的是最大子集的大小， 所以推导公式可以是dp[i][j] = Math.max(dp[i][j], dp[i-zeroNum[i]][j-oneNum[i]])

这里因为使用的滚动二维数组 ，所以需要for三层， 第一层循环数组中的内容， 后面两层循环背包。

实现

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
26
27
28
29
30
31
class Solution {
    public int findMaxForm(String[] strs, int m, int n) {

        //dp[i][j] 表示最多有 i 个 0 和 j 个 1的最大子集长度为dp[i][j]
        int [][]dp = new int[m+1][n+1];

        // 所以递推公式：dp[i][j] = max(dp[i][j], dp[i - zeroNum][j - oneNum] + 1);
        //记录每个字符串中0 和 1 的数量
        int []zone = new int[strs.length];
        int []one = new int[strs.length];
        for(int i= 0 ;i<strs.length; i++){
            for(int j =0 ;j<strs[i].length();j++){
                if(strs[i].charAt(j) == '0'){
                    zone[i]++;
                }
                if(strs[i].charAt(j) == '1'){
                    one[i]++;
                }
            }
        }

        for(int i= 0 ;i < strs.length; i++){
            for(int k = m ; k >= zone[i]; k--){
                for(int j = n ;j>=one[i] ;j--){
                    dp[k][j] = Math.max(dp[k][j], dp[k-zone[i]][j-one[i]]+1);
                }
            }
        }
        return dp[m][n];
    }
}

518 零钱总换

题目：

给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。

示例 1:

  • 输入: amount = 5, coins = [1, 2, 5]
  • 输出: 4

解释: 有四种方式可以凑成总金额:

  • 5=5
  • 5=2+2+1
  • 5=2+1+1+1
  • 5=1+1+1+1+1

示例 2:

  • 输入: amount = 3, coins = [2]
  • 输出: 0
  • 解释: 只用面额2的硬币不能凑成总金额3。

示例 3:

  • 输入: amount = 10, coins = [10]
  • 输出: 1

注意，你可以假设：

  • 0 <= amount (总金额) <= 5000
  • 1 <= coin (硬币面额) <= 5000
  • 硬币种类不超过 500 种
  • 结果符合 32 位符号整数

思路

本题并不是我们之前做的 01 背包类型的问题 ，而是完全背包的问题。

**完全背包 和 01 背包的区别就是 : 完全背包中的数可以重复使用， 而01 背包中的数只能使用1次， 所以01 背包中循环遍历背包的时候，我们都是从大到小遍历的， 这样可以使得每个数都使用一次， 但是 完全背包就需要从小到大遍历， 这样才能实现背包的大小这个变量重复使用。 **

dp[i] ： 表示凑成总金额为 i 的组合数 可以有dp[i]种

由此推导出递推公式为 dp[j] += dp[j-coins[i]]

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public int change(int amount, int[] coins) {
        //递推表达式
        int[] dp = new int[amount + 1];
        //初始化dp数组，表示金额为0时只有一种情况，也就是什么都不装
        dp[0] = 1;
        for (int i = 0; i < coins.length; i++) {
            for (int j = coins[i]; j <= amount; j++) {
                dp[j] += dp[j - coins[i]];
            }
        }
        return dp[amount];
    }
}