本文介绍: 好难 注意初始化以及递推公式 转化为二维数组好理解。1049. 最后一块石头的重量 II。初始化0,注意此题的二维数组含义。分成容量相近的两部分,相减。

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

分成容量相近的两部分,相减

代码随想录

class Solution {
    public int lastStoneWeightII(int[] stones) {
        int sum = 0;
        for(int num : stones) {
            sum += num;
        }
        int target = sum >> 1;//将数组总和分为两部分 向下取整 取小容量为target
        int[] dp = new int[target + 1];//dp[j]指容量为j时所能容纳的最大价值
        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];//大容量所容纳的价值减去小容量容纳的价值
    }
}

 494. 目标和 

好难 注意初始化以及递推公式 转化为二维数组好理解

代码随想录

class Solution {
    public int findTargetSumWays(int[] nums, int target) {
        //分成两部分,正数一部分,负数一部分,根据公式能推导出来他们各自的值。
        //进而转化成给定目标容量,装满背包的方法总数
        int sum = 0;
        for(int num : nums) {
            sum += num;
        }
        int left = (sum + target) / 2;
        if(Math.abs(target) > sum || (sum + target) % 2 == 1) return 0;
        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.一和零  

初始化0,注意此题的二维数组含义

代码随想录

class Solution {
    public int findMaxForm(String[] strs, int m, int n) {
        //01背包问题 实际上是三维问题 压缩为二维滚动数组 维数分别为0和1 的个数
        //dp[i][j]指集合中含有最多i个0 j个1的最大子集个数;
        //此题初始化0
        int[][] dp = new int[m+1][n+1];
        for(String str : strs){
            int x = 0, y = 0;
            for(char ch : str.toCharArray()) {
                if(ch == '0') x++;
                if(ch == '1') y++;
            }
            for(int i = m; i >= x; i--) {
                for(int j = n; j >= y; j--) {
                    dp[i][j] = Math.max(dp[i][j], dp[i - x][j - y] + 1);//若加上str,子集个数加一 作比较
                }
            }
        }
        return dp[m][n];
    }
}

原文地址:https://blog.csdn.net/Tropic____/article/details/135558272

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。

如若转载,请注明出处:http://www.7code.cn/show_55492.html

如若内容造成侵权/违法违规/事实不符,请联系代码007邮箱:suwngjj01@126.com进行投诉反馈,一经查实,立即删除!

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注