1049. 最后一块石头的重量 II
题目链接：力扣
思路
这道题目是让数组中的石头两两相撞，如果重量相同，就可以消除掉， 如果数量不同，就剩下是大重量-小重量
如果一直看的是将其中的每两个石头拿出来相撞，就陷进去了。
从大局看，我们可以将这些石头分成两份，如果这两份重量相同，那最终是可以全部消掉的；如果这两份重量不相同，那最终就是大重量-小重量
那怎么才能将石头分成两份呢，这就跟 416. 分割等和子集 比较相似了
准备一个容量为 sum / 2 的背包，尽可能装石头，一份就是dp[sum/2]；另一份就是 sum - dp[sum/2]。因为sum/2 是向下取整的，所以 sum - dp[sum/2] >= dp[sum/2]，那么 sum - dp[sum/2] - dp[sum/2] 就是我们要求的结果了
背包问题确实可以变成套路，但是要从题目中怎么抽象出背包问题才是更重要的，也是解决代码的第一步
最后一块石头的重量||
class Solution { public int lastStoneWeightII(int[] stones) { // 将石头分成两份，先获取背包容量 int sum = 0; for (int stone : stones) { sum += stone; } int target = sum >> 1; // 创建dp数组 int[] dp = new int[target + 1]; // 默认就初始化了 // 填充dp数组 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 - dp[target] - dp[target]; } }
494. 目标和
题目链接：力扣
思路
0、求什么
真是不看题解毫无思路，看了题解感叹简单，跟416、1049一样，怎么讲问题可以抽象成01背包问题
背包问题中，物品元素是取或者不取
这道题目中，元素是加或者减，都是两种情况
如果是有结果的，那数组中的元素其实被分为两部分，一部分是正数（记做left）；一部分是负数（记做right）
那么就存在：left + right = sum => right = sum- left ①
left - right = target ②
从①代入②中可以得到 left - (sum - left) = target ,从而得到 left = (sum + target) / 2
这样其实就转换成了一个01背包问题，数组中如果有一部分数加起来可以达到 (sum + target) / 2，那就说明这个数组中 可以通过”+“”-“表达式得到 target
(sum + target) / 2 如果除不尽，就说明没有结果
但是这道题目问的不是是否存在这样的表达式，而是求这样的表达式存在多少种，所以在dp[]数组的定义上有所改变
这道题属于：装满背包有多少种方法，而不是能不能装满背包的问题
1、确定dp数组的含义
dp[] 数组 装满容量为 j 的背包，有dp[j] 种方法
2、递推公式
dp[j] 是由 dp[ j - nums[i]] 获得的，这个想起来真的很是抽象
例如：dp[j]，j 为5，
已经有一个1（nums[i]） 的话，有 dp[4]种方法 凑成 dp[5]。
已经有一个2（nums[i]） 的话，有 dp[3]种方法 凑成 dp[5]。
已经有一个3（nums[i]） 的话，有 dp[2]中方法 凑成 dp[5]
已经有一个4（nums[i]） 的话，有 dp[1]中方法 凑成 dp[5]
已经有一个5 （nums[i]）的话，有 dp[0]中方法 凑成 dp[5]
那么凑整dp[5]有多少方法呢，也就是把 所有的 dp[j - nums[i]] 累加起来。
所以求组合类问题的公式，都是类似这种 dp[j] += dp[j - nums[1]]
这个公式在背包解决排列组合问题的时候还会使用
3、初始化dp数组
根基是dp[0],那么dp[0]应该初始化成多少呢？一定要初始化为0
如果初始化dp[0] = 0,那么整个dp[]数组中的元素都是0，因为后面的元素都是从这个根基得到的
dp[0] = 1，理论上也很好解释，装满容量为0的背包，有1种方法，就是装0件物品
dp[j]其他下标对应的数值应该初始化为0，从递归公式也可以看出，dp[j]要保证是0的初始值，才能正确的由dp[j - nums[i]]推导出来
4、遍历顺序
nums放在外循环，target在内循环，且内循环倒序
目标和
class Solution { public int findTargetSumWays(int[] nums, int target) { // 获取数组和 int sum = 0; for (int i : nums) { sum += i; } // 没有方案的情况 if ( (target + sum) % 2 != 0) { return 0; } // 获取背包容量 int bagSize = (target + sum) / 2; // 如果背包容量小于0.这种情况不可以 if (bagSize < 0) { return 0; } // 创建dp数组 int[] dp = new int[bagSize + 1]; // 初始化dp数组 dp[0] = 1; // 遍历填充dp数组 for (int i = 0; i < nums.length; i++) { for (int j = bagSize; j >= nums[i]; j--) { dp[j] += dp[j - nums[i]]; } } // 返回结果 return dp[bagSize]; } }
474.一和零
题目链接：力扣
思路
0、求什么
本题跟之前不同的是背包有两个维度。m个0， n个1
数组中的每一元素还是只使用一次，是01背包问题
本题求的是装满这个背包，最大的物品个数
1、确定dp数组的含义
dp[i][j] 表示 i 个0，j个1，最大背了 dp[i][j] 个物品，最终要求的结果是dp[m][n]
2、递推公式
纯01背包的递推公式 dp[j] = max (dp[j] , dp[j - weight[i]] + value[i])
对于每一个字符串中有 x 个0 ，y 个1
假设现在要装一个字符串，其中有 x 个0 ，y 个1，那我们需要的上一个状态是 dp[ i - x ][ j - y ]，如果要将当前字符串放进来，那就需要 dp[ i - x ][ j - y ] + 1，如果不放就是dp[ i ][ j ]
dp[ i ][ j ] = max(dp[ i ][ j ] , dp[ i - x ][ j - y ] + 1);
3、初始化
dp[ 0 ][ 0 ] 应该初始化成多少呢，此时背包是0+0 = 0 ，能放进去的物品自然是0，所以dp[0][0]=0
非0下标应该怎么初始化呢，非0下标下的肯定不能是0，应该是正数，如果初始化一个很大的数，递推公式的时候，递推公式求得值就会被初始化的值覆盖掉，所以应该初始成0，这样才不会覆盖掉结果
4、遍历顺序
遍历物品：字符串，取出字符中有几个0 ，几个1
遍历背包：倒序遍历
一和零
class Solution { public int findMaxForm(String[] strs, int m, int n) { // 创建dp数组 int[][] dp = new int[m+1][n+1]; // 初始化 // 默认已经全部初始化为0了 // 填充dp数组 for (String s : strs) { // 遍历物品：字符串集合 int zeroNum = 0; // 0的个数 int oneNum = 0; // 1的个数 for (char ch : s.toCharArray()) { // 获取字符串中0和1的个数 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]; } }
