1049. 最后一块石头的重量 II
有一堆石头，用整数数组 stones 表示。其中 stones[i] 表示第 i 块石头的重量。
每一回合，从中选出任意两块石头，然后将它们一起粉碎。假设石头的重量分别为 x 和 y，且 x <= y。那么粉碎的可能结果如下：
如果 x == y，那么两块石头都会被完全粉碎；
如果 x != y，那么重量为 x 的石头将会完全粉碎，而重量为 y 的石头新重量为 y-x。
最后，最多只会剩下一块 石头。返回此石头 最小的可能重量 。如果没有石头剩下，就返回 0。示例 1：
输入：stones = [2,7,4,1,8,1]
输出：1
解释：
组合 2 和 4，得到 2，所以数组转化为 [2,7,1,8,1]，
组合 7 和 8，得到 1，所以数组转化为 [2,1,1,1]，
组合 2 和 1，得到 1，所以数组转化为 [1,1,1]，
组合 1 和 1，得到 0，所以数组转化为 [1]，这就是最优值。
示例 2：输入：stones = [31,26,33,21,40]
输出：5
提示：
1 <= stones.length <= 30
1 <= stones[i] <= 100
状态：看思路就突然明白了
思路：就是跟上一题分割等和子集一样的问题，找到在背包容量是和的一半时另一半的最大容量是多少的问题，与上一题如出一辙，不过这个思路有点难想的到。
class Solution {
public int lastStoneWeightII(int[] stones) {
int sum=0;
for(int a:stones){
sum+=a;
}
int half=sum%2==0?sum/2:(sum/2)+1;
int[] dp=new int[half+1];
for(int i=0;i<stones.length;i++){
for(int j=half;j>=0;j--){
if (j-stones[i]<0) break;
dp[j]=Math.max(dp[j],(dp[j-stones[i]]+stones[i]));
}
}
System.out.print(Arrays.toString(dp));
return Math.abs(sum-2*dp[half]);
}
}494. 目标和
给你一个非负整数数组 nums 和一个整数 target 。
向数组中的每个整数前添加 '+' 或 '-' ，然后串联起所有整数，可以构造一个 表达式 ：
例如，nums = [2, 1] ，可以在 2 之前添加 '+' ，在 1 之前添加 '-' ，然后串联起来得到表达式 "+2-1" 。
返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。示例 1：
输入：nums = [1,1,1,1,1], target = 3
输出：5
解释：一共有 5 种方法让最终目标和为 3 。
-1 + 1 + 1 + 1 + 1 = 3
+1 - 1 + 1 + 1 + 1 = 3
+1 + 1 - 1 + 1 + 1 = 3
+1 + 1 + 1 - 1 + 1 = 3
+1 + 1 + 1 + 1 - 1 = 3
示例 2：输入：nums = [1], target = 1
输出：1
提示：
1 <= nums.length <= 20
0 <= nums[i] <= 1000
0 <= sum(nums[i]) <= 1000
-1000 <= target <= 1000
状态：没做出来
思路：这题是可以转化成使背包容量刚刚好的方法有多少种。正数是p，那负数就是-（sum-p）,这两个之和是target就可以了，也即p=(sum+target)/2。dp[i]表示容量为i时有多少种组成方式。递推式就是dp[j]=dp[j]+dp[j-nums[i]];因为当前元素是nums[j]时背包容量没加前是dp[i-nums[j]]这个容量的方法数+dp[i]的方法数就得成了。
class Solution {
public int findTargetSumWays(int[] nums, int target) {
int sum=0;
for(int a:nums){
sum+=a;
}
if((target+sum)%2==1) return 0;
if(sum+target<0) return 0;
int p=(target+sum)/2;
int[] dp=new int[p+1];
dp[0]=1;
for(int i=0;i<nums.length;i++){
for(int j=p;j>=nums[i];j--){
dp[j]=dp[j]+dp[j-nums[i]];
}
}
System.out.println(Arrays.toString(dp));
return dp[p];
}
}感想：0-1背包还是比较难理解的，明天再把一和零补一下，今天先这样，0-1背包现在做起来分了几种，第一种就是经典的最大价值问题，第二种是上面那个求最大方法数的。