【5.31 代随_43day】最后一块石头的重量 II、目标和、一和零-Toy模板网

这篇具有很好参考价值的文章主要介绍了【5.31 代随_43day】最后一块石头的重量 II、目标和、一和零。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

最后一块石头的重量 II

力扣连接：1049. 最后一块石头的重量 II（中等）

1.方法

和 416. 分割等和子集 (opens new window) 非常像了

图解步骤

代码

class Solution {
    public int lastStoneWeightII(int[] stones) {
        int sum = Arrays.stream(stones).sum();
        int target = sum/2;
        
        int[] dp = new int[target+1];

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

        int other = sum-dp[target];//另一堆石头

        return other-dp[target];
    }
}

目标和

力扣连接：494. 目标和（中等）

1.方法

确定dp数组以及下标的含义
dp[j] 表示：填满j（包括j）这么大容积的包，有dp[j]种方法
确定递推公式
只要搞到nums[i]，凑成dp[j]就有dp[j - nums[i]] 种方法。
例如：dp[j]，j 为5，
已经有一个1（nums[i]）的话，有 dp[4]种方法凑成容量为5的背包。
已经有一个2（nums[i]）的话，有 dp[3]种方法凑成容量为5的背包。
已经有一个3（nums[i]）的话，有 dp[2]中方法凑成容量为5的背包
已经有一个4（nums[i]）的话，有 dp[1]中方法凑成容量为5的背包
已经有一个5 （nums[i]）的话，有 dp[0]中方法凑成容量为5的背包
那么凑整dp[5]有多少方法呢，也就是把所有的 dp[j - nums[i]] 累加起来。

图解步骤

【5.31 代随_43day】最后一块石头的重量 II、目标和、一和零

关键点：

if (abs(target) > sum) return 0; // 此时没有方案
f ((target + sum) % 2 != 0) return 0; // 此时没有方案

代码

class Solution {
    public int findTargetSumWays(int[] nums, int target) {
        int sum = Arrays.stream(nums).sum();

        //target过大的情况
        if(target<0 && Math.abs(target)>sum) return 0;

        //无法整除的情况
        if((target+sum)%2!=0) return 0;

        int left = (target+sum)/2;
        //背包容量为j时，有dp[j]种方法
        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. 一和零（中等）

确定dp数组（dp table）以及下标的含义
dp[i][j]：最多有i个0和j个1的strs的最大子集的大小为dp[i][j]。
确定递推公式
dp[i][j] 可以由前一个strs里的字符串推导出来，strs里的字符串有zeroNum个0，oneNum个1。
dp[i][j] 就可以是 dp[i - zeroNum][j - oneNum] + 1。
然后我们在遍历的过程中，取dp[i][j]的最大值。
所以递推公式：dp[i][j] = max(dp[i][j], dp[i - zeroNum][j - oneNum] + 1);

图解步骤

【5.31 代随_43day】最后一块石头的重量 II、目标和、一和零文章来源地址https://www.toymoban.com/news/detail-470543.html

代码

class Solution {
    public int findMaxForm(String[] strs, int m, int n) {
        int[][] dp = new int[m+1][n+1];

        for(String str: strs){
            int zeroNum = 0;
            int oneNum = 0;
            for(char ch: str.toCharArray()){
                if(ch=='1'){
                    oneNum++;
                }else{
                    zeroNum++;
                }
            }

            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];
    }
}