1049
题目:
有一堆石头,用整数数组 stones
表示。其中 stones[i]
表示第 i
块石头的重量。
每一回合,从中选出任意两块石头,然后将它们一起粉碎。假设石头的重量分别为 x
和 y
,且 x <= y
。那么粉碎的可能结果如下:
- 如果
x == y
,那么两块石头都会被完全粉碎; - 如果
x != y
,那么重量为x
的石头将会完全粉碎,而重量为y
的石头新重量为y-x
。
最后,最多只会剩下一块 石头。返回此石头 最小的可能重量 。如果没有石头剩下,就返回 0
。
题目链接:1049. 最后一块石头的重量 II - 力扣(LeetCode)
思路:
如果想要最后剩下的可能重量最小,那么就要把石头分成两批,两批的重量最相近,每一次两块石头都分别来自两批中,这样最后的石头才能最轻。这样就回归01背包问题,石头的重量是weight也是value。
代码:
class Solution {
public int lastStoneWeightII(int[] stones) {
int sum=0;
for(int i=0;i<stones.length;i++)
sum=sum+stones[i];
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=0;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]);
}
}
494
题目:
给你一个非负整数数组 nums
和一个整数 target
。
向数组中的每个整数前添加 '+'
或 '-'
,然后串联起所有整数,可以构造一个 表达式 :
- 例如,
nums = [2, 1]
,可以在2
之前添加'+'
,在1
之前添加'-'
,然后串联起来得到表达式"+2-1"
。
返回可以通过上述方法构造的、运算结果等于 target
的不同 表达式 的数目。
思路:
这道题相当于把数组分为+集和-集,并要满足两者之差等于target,这样就可以得到+集的总和,然后找到+集有多少种方案,01背包,dp[target]就是装满target的方法,他是dp[j-num[i]]的累加。
代码:
class Solution {
public int findTargetSumWays(int[] nums, int target) {
int sum=0;
for(int i=0;i<nums.length;i++)
sum=sum+nums[i];
if(Math.abs(target)>sum) return 0;
if((target+sum)%2!=0) return 0;
int bagsize =(target+sum)/2;
int[] dp =new int[bagsize+1];
dp[0]=1;
for(int i=0;i<nums.length;i++)
for(int j=bagsize;j>=nums[i];j--)
dp[j]=dp[j]+dp[ j-nums[i] ];
return dp[bagsize];
}
}
474
题目:
给你一个二进制字符串数组 strs
和两个整数 m
和 n
。
请你找出并返回 strs
的最大子集的长度,该子集中 最多 有 m
个 0
和 n
个 1
。
如果 x
的所有元素也是 y
的元素,集合 x
是集合 y
的 子集 。
思路:
可以把字符串想象为物品,把m,n想为两种不同的负重或者说是限制,然后个数为价值。
代码:
class Solution {
public int findMaxForm(String[] strs, int m, int n) {
//dp[i][j]表示i个0和j个1时的最大子集
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];
}
}