本文介绍: 好难 注意初始化以及递推公式 转化为二维数组好理解。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进行投诉反馈,一经查实,立即删除!
声明:本站所有文章,如无特殊说明或标注,均为本站原创发布。任何个人或组织,在未征得本站同意时,禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。如若本站内容侵犯了原著者的合法权益,可联系我们进行处理。