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

最后一块石头的重量 II

class Solution {
    // dp[j] 容量为j 的背包，最多可以背最大重量为dp[j]。
    // dp[j] = Math.max(dp[j], dp[j - stones[i]] + stones[i])
    // 求 sum/2 = target 的背包最多能装多少，就可以求  sum - dp[target] 最少能装多少
    // 就可以求 最小的可能重量  (sum - dp[target]) - dp[target] 
    public int lastStoneWeightII(int[] stones) {
        int sum = 0;
        for (int i : stones) {
            sum += 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 - 2 * dp[target];
    }
}

class Solution {
    public int lastStoneWeightII(int[] stones) {
        int sum = 0;
        for (int s : stones) {
            sum += s;
        }

        int target = sum / 2;
        int[][] dp = new int[stones.length][target + 1];

        for (int j = stones[0]; j <= target; j++) {
            dp[0][j] = stones[0];
        }

        for (int i = 1; i < stones.length; i++) {
            for (int j = 1; j <= target; j++) {
                if (j >= stones[i]) {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - stones[i]] + stones[i]);
                } else {
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }

        return (sum - dp[stones.length - 1][target]) - dp[stones.length - 1][target];
    }
}

目标和

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

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

先分析题目：

本题要如何使表达式结果为target，
既然为target，那么就一定有 left组合 - right组合 = target。
left + right = sum，而sum是固定的。right = sum - left
公式来了， left - (sum - left) = target 推导出 left = (target + sum)/2 。
target是固定的，sum是固定的，left就可以求出来。
此时问题就是在集合nums中找出和为left的组合。

回溯方法中的组合问题，但会超时

class Solution {
    // left组合 - right组合 = target。
    // left - (sum - left) = target 推导出 left = (target + sum)/2 。
    // 此时问题就是在集合nums中找出和为left的组合。
    public int findTargetSumWays(int[] nums, int target) {
        int sum = 0;
        for (int i = 0; i < nums.length; i++) sum += nums[i];

        if (target > sum) return 0;
        if ((target + sum) % 2 == 1) return 0;
        int bagSize = (target + sum) / 2;  // bagsize就是要求的和
        Arrays.sort(nums);
        backtracking(nums, bagSize, 0, 0);
        return result.size();
    }

    List<List<Integer>> result = new ArrayList<>();;
    List<Integer> path = new ArrayList<>();;

    private void backtracking(int[] nums, int target, int sum, int startIndex) {
        if (sum == target) result.add(new ArrayList<>(path));

        for (int i = startIndex; i < nums.length && sum + nums[i] <= target; i++) {
            sum += nums[i];
            path.add(nums[i]);
            backtracking(nums, target, sum, i+1);
            sum -= nums[i];
            path.removeLast();
        }
    }
}

动态规划 01 背包问题

假设加法的总和是 x，那么减法对应的总和就是 sum - x

所以要求的是 x - (sum - x) = target

x = (target + sum) / 2

问题就转化为，装满容量为x的背包，有几种方法。
之前的背包问题是：求容量为 j 的背包，最多能装多少
本题则是装满有几种方法组合问题
- dp[j] : 填满 j 这么大容积的包，有dp[j]种方法
- dp[j] += dp[j - nums[i]]
- dp[0] = 1
- nums放在外循环，target在内循环，且内循环倒序。

在这里插入图片描述

class Solution {
    // dp[j] : 填满 j 容积的包，有 dp[j] 种方法
    // dp[j] += dp[j - nums[i]]   求组合类问题的公式，都是类似这种：
    // dp[0] = 1
    // nums放在外循环，target在内循环，且内循环倒序。
    public int findTargetSumWays(int[] nums, int target) {
        int sum = 0;
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
        }
        if (target > sum) return 0;
        if (target < 0 && sum < -target) return 0;
        if ((target + sum) % 2 != 0) return 0;
        int size = (target + sum) / 2;
        int[] dp = new int[size + 1];
        dp[0] = 1;
        for (int i = 0; i < nums.length; i++) {
            for (int j = size; j >= nums[i]; j--) {
                dp[j] += dp[j - nums[i]];
            }
        }
        return dp[size];
    } 
}

class Solution {
    public int findTargetSumWays(int[] nums, int target) {
        // 01背包应用之“有多少种不同的填满背包最大容量的方法“
        // 易于理解的二维数组解法及详细注释

        int sum = 0;
        for (int n: nums) sum += n;
        if (sum < Math.abs(target)) return 0;

        if ((sum + target) % 2 != 0) return 0;

        int left = (sum + target) / 2;

        // dp[i][j]：遍历到数组第i个数时， left为j时的能装满背包的方法总数
        int[][] dp = new int[nums.length][left + 1];

        // 初始化最上行（dp[0][j])，当nums[0] == j时（注意nums[0]和j都一定是大于等于零的，因此不需要判断等于-j时的情况），有唯一一种取法可取到j，dp[0][j]此时等于1
        // nums[0] <= left 时， 取 nums[0] == j 这个时候 dp 数组= 1 
        // 其他情况dp[0][j] = 0
        // java整数数组默认初始值为0
        if (nums[0] <= left) dp[0][nums[0]] = 1;

        // 初始化最左列（dp[i][0])
        // 当从nums数组的索引0到i的部分有n个0时（n > 0)，每个0可以取+/-，因此有2的n次方中可以取到j = 0的方案
        // n = 0说明当前遍历到的数组部分没有0全为正数，因此只有一种方案可以取到j = 0（就是所有数都不取）

        int numZeros = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == 0) {
                numZeros++;
            }
            dp[i][0] = (int) Math.pow(2, numZeros);
        }

        // 递推公式
        // 当nums[i] > j时，这时候nums[i]一定不能取，所以是dp[i - 1][j]种方案数
        // nums[i] <= j时，num[i]可取可不取，因此方案数是dp[i - 1][j] + dp[i - 1][j - nums[i]]
        for (int  i = 1;  i < nums.length; i++) {
            for (int j = 1; j <= left; j++) {
                if (nums[i] > j) {
                    dp[i][j] = dp[i - 1][j];
                }
                else {
                    dp[i][j] = dp[i - 1][j] + dp[i - 1][j - nums[i]];
                }
            }
        }
        return dp[nums.length - 1][left];
    }
}

一和零

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

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

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

背包两个维度 m个0 和 n 个1
物品，价值每个都是 1
典型的01背包

class Solution {
    // dp[i][j] 最多有 i 个 0 和 j 个 1 的strs 的最大子集的大小为 dp[i][j]
    // dp[i][j] = Math.max(dp[i][j], dp[i - zeroNum][j - oneNum] + 1)
    // 物品的重量有两个维度
    // 初始为0，保证递推的时候dp[i][j]不会被初始值覆盖。
    // 外层for循环遍历物品，内层for循环遍历背包容量且从后向前遍历
    // 物品就是strs里的字符串，背包容量就是题目描述中的m和n。
    public int findMaxForm(String[] strs, int m, int n) {
        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];
    }
}