题目难度：中等
有一堆石头，每块石头的重量都是正整数。
每一回合，从中选出任意两块石头，然后将它们一起粉碎。假设石头的重量分别为?x 和?y，且?x <= y。那么粉碎的可能结果如下：
如果?x == y，那么两块石头都会被完全粉碎；
如果?x != y，那么重量为?x?的石头将会完全粉碎，而重量为?y?的石头新重量为?y-x。
最后，最多只会剩下一块石头。返回此石头最小的可能重量。如果没有石头剩下，就返回 0。
示例：
解释：
提示：
? ? ? ? 我会想着去相减获取最小的值
? ? ? ? dp存最小值
? ? ? ? 01背包获取的是最大值
????????01背包获取的是最大值
? ? ? ? 将所有的石头加起来，获取石头总和的一半
? ? ? ? 背包:? ?选中石头0~i 达到背包容量为石头总和的一半的最大值是多少
? ? ? ? weight[i] 石头大小
? ? ? ? value[j] 石头大小
? ? ? ? 动规五部曲，很快的写出解题思路
? ? ? ? 1确定dp数组以及对应下标的含义
????????dp[j] 代表选中0~i达到背包容量j时的最大值
? ? ? ?背包容量：0~石头总和的一半
????????2确定递推公式
? ? ? ? dp[j] = Math.max(dp[j],dp[j-stones[i]]+stones[i]);
????????3dp数组初始化
? ? ? ? 都为0
? ? ? ? 4确定遍历顺序
? ? ? ? 先物品后背包
????????从后往前
????????5手动推导dp数组
? ? ? ? 6打印dp数组
? ? ? ??
? ? ? ? return sum-2dp[target]
class Solution {
public int lastStoneWeightII(int[] stones) {
// 我的思路 想直接获取最小值是错误的, 01背包获取的是最大值
// dp[j] 选中0~i块石头在j这个空间内的最小重量值
//卡哥思路
// 本题返回的是最小重量，也就是差值的最小重量
// 可以把所有石头重量求和，获取总重量
// 当我们可以达到总重量的一半时，就为0
// 求当背包重量到达总重量一半时，背包可以容纳的最大值，就转换成背包问题了
// dp数组的确定以及每个下标的含义
// 选中0~i块石头 ，当背包到达容量j时可以容纳的最大值为多少
// 确定递推公式
// 上一层 or 上一层-当前层的weight后加上当前层的值
// dp[j] = Math.max(dp[j],dp[j-stones[j]]+stones[i]);
// dp的初始化
// 开始都为0，从石头0开始逐个遍历
// 确定遍历顺序
// 从后往前
// 手动推导dp数组
int sum=0;
for(int i=0;i<stones.length;i++){
sum+=stones[i];
}
int target = sum/2;
int dp[] = new int[target+1];
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];
}
}
难度：中等
给定一个非负整数数组，a1, a2, ..., an, 和一个目标数，S。现在你有两个符号?+?和?-。对于数组中的任意一个整数，你都可以从?+?或?-中选择一个符号添加在前面。
返回可以使最终数组和为目标数 S 的所有添加符号的方法数。
示例：
解释：
一共有5种方法让最终目标和为3。
提示：
? ? ? ? 想着用dp，但没思路
? ? ? ? left+right = sum
? ? ? ? left-right = target
? ? ? ? 2left = sum+target
? ? ? ? 则left = (sum+target)/2
? ? ? ? 则 我们需要计算的是
????????达到目标和为left的总的方法数
????????01背包获取的是最大值
? ? ? ? 将所有的石头加起来，获取石头总和的一半
? ? ? ? 背包:? ?选中0~i 达到目标和为j 有多少种方法
? ? ? ?
? ? ? ? 动规五部曲，很快的写出解题思路
? ? ? ? 1确定dp数组以及对应下标的含义
????????dp[j] 代表选中0~i达到背包容量j时有多少种方法
? ? ? ?背包容量：0~left
????????2确定递推公式
? ? ? ? dp[j]+=dp[j-nums[i]]
? ? ? ? 若当前选中的为nums[i] 则需要找到dp[j-nums[i]]种方法，才能凑成 j?
????????3dp数组初始化
? ? ? ? dp[0]=1? ? 因为 最开始选中的dp[nums[0]]，有dp[0]种方法凑成?则dp[0]+dp[nums[0]] = 1
? ? ? ? 4确定遍历顺序
? ? ? ? 先物品后背包
????????从后往前
????????5手动推导dp数组
? ? ? ? 6打印dp数组
? ? ? ??
? ? ? ? 从? j=nums[i] 开始? ，到j<=left 结束
? ? ? ? 看有多少种方法凑成left
class Solution {
public int findTargetSumWays(int[] nums, int target) {
// 让nums中的和等于sum
// 观察一下关系
// left-right = target
// left 为左半边的和，right为右半边的和
// left+right = sum
// right = sum-left
// target = left-sum+left
// 2 left = target+sum
// left = (target+sum)/2
// dp数组
// 确定dp数组和每个下标的含义
// 背包 0~i之间 填满j的最大空间
// 求出left，计算0~i之间能满足空间j的数量 j属于0~left
// 确定递推公式
// 代表能达到dp[j]
// 选中nums[i] 若要满足填满空间j ，则需要 num[i]的值+dp[j-nums[i]] 这么多个才能填满
// 在上一层的dp[j]的基础上加上dp[j-nums[i]] 就是这一层能完成j的总数了
// 每一行是i 每一列是j 到第i行时，从0~i-1得到的结果中判断第i行的nums[i] 有多少个可以满足j
// dp[j]+=dp[j-nums[i]]
// 把之前的能达成的数量都加上
// dp数组初始化
// 从后往前，同时dp[0]=1
// 若nums[0] = j ，则dp[j] += dp[j-nums[0]] = dp[0] = 1 满足j的只有1个
// dp数组遍历顺序
// 从后往前
// 举例推导dp数组
//
int sum=0;
for(int i=0;i<nums.length;i++){
sum+=nums[i];
}
if((sum+target)%2==1){
return 0;
}
//这个边界条件没注意到
if(Math.abs(target)>sum){
return 0;
}
int left = (sum+target)/2;
int[] dp = new int[left+1];
dp[0] = 1;
for(int i=0;i<nums.length;i++){
//前面的j 都比nums[i] 要小，无法用nums[i]构成j
for(int j=left;j>=nums[i];j--){
dp[j]=dp[j]+dp[j-nums[i]];
}
}
return dp[left];
}
}给你一个二进制字符串数组 strs 和两个整数 m 和 n 。
请你找出并返回 strs 的最大子集的大小，该子集中 最多 有 m 个 0 和 n 个 1 。
如果 x 的所有元素也是 y 的元素，集合 x 是集合 y 的 子集 。
示例 1：
输入：strs = ["10", "0001", "111001", "1", "0"], m = 5, n = 3
输出：4
解释：最多有 5 个 0 和 3 个 1 的最大子集是 {"10","0001","1","0"} ，因此答案是 4 。 其他满足题意但较小的子集包括 {"0001","1"} 和 {"10","1","0"} 。{"111001"} 不满足题意，因为它含 4 个 1 ，大于 n 的值 3 。
示例 2：
提示：
? ? ? ? 想着用dp，
? ? ? ? 1 不知道怎么处理这些string
? ? ? ? 2 这里有二维? 一个m 一个n
? ? ? ? 遍历字符数组，看每个字符串中0 和1 的个数
? ? ? ? 背包:? ?选中(0,0)~(i,j)?达到目标和为(m,n) 的子集的个数
? ? ? ?weight 为 0和1 的个数
? ? ? ? value 统一为1 选中则+1
????????动规五部曲，很快的写出解题思路
? ? ? ? 1确定dp数组以及对应下标的含义
????????dp[i][j] i代表m
? ? ? ?背包容量：0，0 ~ （m,n）
????????2确定递推公式
? ? ? ? 若不选则还是之前的
? ? ? ? 若选中则+1
? ? ? ? dp[I][j]=Math.max(dp[i][j],dp[i-zeroNum][j-oneNum]+1)
? ? ? ? 若当前选中的为str[i] 则需要找到dp[i-0的个数][j-1的个数]种方法，才能凑成 dp[i][j]
????????3dp数组初始化
? ? ? ? 都为0
? ? ? ? 4确定遍历顺序
? ? ? ? 先物品后背包
????????从后往前
????????5手动推导dp数组
? ? ? ? 6打印dp数组
? ? ? ??
? ? ? ?用string转成char数组来记录0的个数和1 的个数
class Solution {
public int findMaxForm(String[] strs, int m, int n) {
// str 的最大的子集的长度
// 使用一个map记录数组有多少个0和1？
// 卡哥思路 dp 用一个二维数组，dp[m][n] 记录 满足子集m个0和n个1的最大个数
// 背包 满足 m个0和n个1 的个数？
// 计算有多少个0 和多少个1
// 子集中的每个元素 最多有m个0 和n个1
// dp数组和每个下标的定义
// dp记录填满背包的[m][n]最大个数
// 确定递推公式
// dp[m][n]=Math.max(dp[m][n],dp[m-oneNum][n-oneNum]);
// dp数组的初始化
// 都为0
// 确定遍历顺序
// 从后往前
// 手动推导dp数组
int[][] dp = new int[m+1][n+1];
for(String str:strs){
int zeroNum=0;
int oneNum=0;
for(int i=0;i<str.length();i++){
if(str.charAt(i)=='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];
}
}