代码随想录算法训练营第43天

今日任务

● 1049. 最后一块石头的重量 II ● 494. 目标和 ● 474.一和零

链接：https://docs.qq.com/doc/DUEVMRHZOemN5S2Vm (opens in a new tab)

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

自己想法

将石头分为尽可能重量相等的两堆，可以使得两堆石头的重量差最小。

因为分开两堆后，不管怎么粉碎，最后一块石头的重量都是两堆石头的重量差。

所以问题转化为：将数组内的数看作物品，其价值和重量都是这个数，

将数组和的一半（向下取整）看作背包的容量，转化为01背包问题。

最终返回数组和减去两倍背包问题的最大值。

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

494. 目标和

题解想法

将数组分为两部分，一部分是加号的数，一部分是减号的数。

本题需要将背包装满，在求装满背包有几种方法的情况下，递推公式一般为：dp[j] += dp[j - nums[i]];

dp[j]表示容量为j的背包有多少种方法装满。外层循环表示遍历物品，内层j循环表示遍历背包容量。

class Solution {
    public int findTargetSumWays(int[] nums, int target) {
        //    bag - (sum - bag) = target
        // -> bag = (target + sum) / 2
        // -> bag必须为整数; bag必须大于等于0
        int twin_bag = Arrays.stream(nums).sum() + target;
        if (twin_bag % 2 != 0) return 0;
        int bag = twin_bag / 2;
        if (bag < 0) return 0;
 
        int[] dp = new int[bag + 1];
        dp[0] = 1;
 
        for (int i = 0; i < nums.length; i++) {
            for (int j = bag; j >= nums[i]; j--) {
                dp[j] += dp[j - nums[i]];
            }
        }
 
        return dp[bag];
    }
}

474.一和零

题解想法

本题是一个多维费用的01背包问题。

dp[i][j]最多有i个0和j个1的strs的最大子集的大小。外层循环表示遍历物品，内层i和j循环表示遍历背包容量。

class Solution {
    public int findMaxForm(String[] strs, int m, int n) {
        int[][] dp = new int[m + 1][n + 1];
        for (String str : strs) {
            int countZero = 0;
            int countOne = 0;
            for (char c : str.toCharArray()) {
                if (c == '0') {
                    countZero++;
                } else if (c == '1') {
                    countOne++;
                }
            }
 
            for (int i = m; i >= countZero; i--) {
                for (int j = n; j >=countOne ; j--) {
                    dp[i][j] = Math.max(dp[i][j], dp[i - countZero][j - countOne] + 1);
                }
            }
        }
        return dp[m][n];
    }
}