416 分割等和子集
题目：
题目难易：中等
给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
注意: 每个数组中的元素不会超过 100 数组的大小不会超过 200
示例 1:
输入: [1, 5, 11, 5]
输出: true
解释: 数组可以分割成 [1, 5, 5] 和 [11].
示例 2:
输入: [1, 2, 3, 5]
输出: false
解释: 数组不能分割成两个元素和相等的子集.
提示：
1 <= nums.length <= 200
1 <= nums[i] <= 100
思路：
题目中要求 ：使得两个子集的元素和相等。 那么就可以对数组中的所有元素求和， 如果sum%2 != 0 ,那么就直接返回false 。原因这里就不多了， 奇数怎么可能有两个相等的子集和呢?
如此一来就可以将本体转换为求数组中的元素之和能否等于 sum/2了。 这样就可以用到动态规划的思路来进行解题了。
dp[i] 表示 背包容量为 i 的背包， 所能容纳的物体的最大价值是 dp[i]
这里我们将数组中元素得到的最大子集和 抽象成为背包的最大价值 。
最后通过比较 dp[target] == target 来返回最后的结果即可。
推导公式 可以通过dp[j] = Math.max(dp[j], dp[j - weight[i]] + values[i])(**放与不放的状态取最大值)**得出 ，因为这里获取的是数字， 所以他的weight 和 value都是nums[i] 。按照上述的推导公式就可以得出。
实现
class Solution { public boolean canPartition(int[] nums) { //只需要找到每个数组中为sum/2的 ，如果出现sum为奇数，那么就返回false int sum = 0; for(int i =0 ;i <nums.length;i++){ sum += nums[i]; } if(sum % 2 != 0){ return false; } //找到累加结果为target即可 int target = sum /2 ; //dp[i]数组的含义是:容量为i 的背包 ，所能容纳的物品的最大价值为dp[i] //换算到本题就是 容量为i的背包， 所能累加的数字的最大和为dp[i] 最后如果dp[target] == target 那么就返回true else false int []dp = new int[target+1]; //先遍历每一个数字 for(int i =0; i < nums.length; i++){ for(int j = target; j >= nums[i] ;j--){ dp[j] = Math.max(dp[j] , dp[j-nums[i]] + nums[i]); // System.out.println("dp["+j+"]的结果是= "+dp[j]); } } return target == dp[target]; } }
1049 最后一块石头的重量
题目：
题目难度：中等
有一堆石头，每块石头的重量都是正整数。
每一回合，从中选出任意两块石头，然后将它们一起粉碎。假设石头的重量分别为 x 和 y，且 x <= y。那么粉碎的可能结果如下：
如果 x == y，那么两块石头都会被完全粉碎；
如果 x != y，那么重量为 x 的石头将会完全粉碎，而重量为 y 的石头新重量为 y-x。
最后，最多只会剩下一块石头。返回此石头最小的可能重量。如果没有石头剩下，就返回 0。
示例：
输入：[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]，这就是最优值。
提示：
1 <= stones.length <= 30
1 <= stones[i] <= 1000
实现
本题和上道题是一摸一样的套路， 仅仅是最后取得结果不同， 这需要知道最后还剩的最小 ，那么就是使用sum - dp[target] - dp[target]从而得到。
class Solution { //可以将本题看成两个数相减， left - right = target //因为两个数的 left + right = sum 这个sum是固定的 那么就可以通过这两个式子推导出 //left = ( sum + target ) /2 //所以本题就变成了求和为left的种类数了 public int findTargetSumWays(int[] nums, int target) { //dp数组的含义: 向背包容量为 i 的背包中添加nums[i] 的物品， 背包的最大价值是dp[i] //这里的最大价值就是表达式的种类数 int sum = 0; for(int i =0 ;i < nums.length;i++){ sum += nums[i]; } if ( target < 0 && sum < -target) return 0; if((sum + target)%2 != 0 ) return 0; int left = (sum + target) / 2 ; 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]; } }
494 目标和
题目：
难度：中等
给定一个非负整数数组，a1, a2, …, an, 和一个目标数，S。现在你有两个符号 + 和 -。对于数组中的任意一个整数，你都可以从 + 或 -中选择一个符号添加在前面。
返回可以使最终数组和为目标数 S 的所有添加符号的方法数。
示例：
输入：nums: [1, 1, 1, 1, 1], S: 3
输出：5
解释：
-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
一共有5种方法让最终目标和为3。
提示：
数组非空，且长度不会超过 20 。
初始的数组的和不会超过 1000 。
保证返回的最终结果能被 32 位整数存下
提示：
1 <= nums.length <= 20
0 <= nums[i] <= 1000
0 <= sum(nums[i]) <= 1000
-1000 <= target <= 1000
思路 ：
二刷才理解这道题的做法，所以本次刷题的时候还是没做出来。 因为单纯的从题目本身是无法联想到怎么应用到动态规划的。
从题目中看， 也就是一个两位数相减的问题， 加号我们这里省略， 所以 就可以通过 left - right == target left 是这个数组的一部分内容相加得到； 同理 right 是数组的另一部分相加得到 。然后就可以看出 目标数就是两个数组子集和 相减得到的。 同时，这两个数 相加的结果一定是整个数组的sum 。因此就可以得到left + right == sum sum是固定的。
从上述的两个式子中，我们可以得到left = (sum + target) /2 。突然间， 问题就回归到了 数组中的内容求和 等于 left 有几种方法了。 这样就可以联系到动态规划的思路了 。
dp[i]表示 内容求和为 i 的方法有 dp[i]种 .
按照思路就可以得到递推公式 dp[j] += dp[j - nums[i]]。
注意：这里需要排除target < 0 && sum + target < 0 的情况， 因为数组中的每个数都是大于 0 的如果sum + target < 0 那么就说明target 是小于 -sum的 。所以是不存在的。
实现
class Solution { //可以将本题看成两个数相减， left - right = target //因为两个数的 left + right = sum 这个sum是固定的 那么就可以通过这两个式子推导出 //left = ( sum + target ) /2 //所以本题就变成了求和为left的种类数了 public int findTargetSumWays(int[] nums, int target) { //dp数组的含义: 向背包容量为 i 的背包中添加nums[i] 的物品， 背包的最大价值是dp[i] //这里的最大价值就是表达式的种类数 int sum = 0; for(int i =0 ;i < nums.length;i++){ sum += nums[i]; } if ( target < 0 && sum < -target) return 0; if((sum + target)%2 != 0 ) return 0; int left = (sum + target) / 2 ; 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 一和零
题目：
给你一个二进制字符串数组 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：
输入：strs = [“10”, “0”, “1”], m = 1, n = 1
输出：2
解释：最大的子集是 {“0”, “1”} ，所以答案是 2 。
提示：
1 <= strs.length <= 600
1 <= strs[i].length <= 100
strs[i] 仅由 ‘0’ 和 ‘1’ 组成
1 <= m, n <= 100
思路
和上道题一样， 这道题还是2刷都未做出来 ，还是刚开始的固有思维没有发散到通过其他方法来转换到动态规划， 所以导致题目一转换就忘了怎么出发。
strs 的最大子集的大小，该子集中 最多 有 m 个 0 和 n 个 1 。 用滚动数组(一维数组)的方法是很难想出来的，还是需要使用二维数组 ，因为这里的变量有两个， 所以需要滚动二维数组(自创词) 来解决。
dp[i][j] : 就可以表示为 有 i个 0 和 j 个 1 组成的最大子集的大小是dp[i][j]
但是这里子集的 0 和 1 都不好确定， 我这边使用的是一种笨办法 ，通过两个数组（zeroNum and oneNum）来记录 strs 中每个元素中的 0 和 1 的个数
这样我们在遍历的时候就可以直接拿来用了。（其实还有更好的）
求的是最大子集的大小， 所以推导公式可以是dp[i][j] = Math.max(dp[i][j], dp[i-zeroNum[i]][j-oneNum[i]])
这里因为使用的滚动二维数组 ，所以需要for三层， 第一层循环数组中的内容， 后面两层循环背包。
实现
class Solution { public int findMaxForm(String[] strs, int m, int n) { //dp[i][j] 表示最多有 i 个 0 和 j 个 1的最大子集长度为dp[i][j] int [][]dp = new int[m+1][n+1]; // 所以递推公式：dp[i][j] = max(dp[i][j], dp[i - zeroNum][j - oneNum] + 1); //记录每个字符串中0 和 1 的数量 int []zone = new int[strs.length]; int []one = new int[strs.length]; for(int i= 0 ;i<strs.length; i++){ for(int j =0 ;j<strs[i].length();j++){ if(strs[i].charAt(j) == '0'){ zone[i]++; } if(strs[i].charAt(j) == '1'){ one[i]++; } } } for(int i= 0 ;i < strs.length; i++){ for(int k = m ; k >= zone[i]; k--){ for(int j = n ;j>=one[i] ;j--){ dp[k][j] = Math.max(dp[k][j], dp[k-zone[i]][j-one[i]]+1); } } } return dp[m][n]; } }
518 零钱总换
题目：
给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。
示例 1:
输入: amount = 5, coins = [1, 2, 5]
输出: 4
解释: 有四种方式可以凑成总金额:
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1
示例 2:
输入: amount = 3, coins = [2]
输出: 0
解释: 只用面额2的硬币不能凑成总金额3。
示例 3:
输入: amount = 10, coins = [10]
输出: 1
注意，你可以假设：
0 <= amount (总金额) <= 5000
1 <= coin (硬币面额) <= 5000
硬币种类不超过 500 种
结果符合 32 位符号整数
思路
本题并不是我们之前做的 01 背包类型的问题 ，而是完全背包的问题。
**完全背包 和 01 背包的区别就是 : 完全背包中的数可以重复使用， 而01 背包中的数只能使用1次， 所以01 背包中循环遍历背包的时候，我们都是从大到小遍历的， 这样可以使得每个数都使用一次， 但是 完全背包就需要从小到大遍历， 这样才能实现背包的大小这个变量重复使用。 **
dp[i] ： 表示凑成总金额为 i 的组合数 可以有dp[i]种
由此推导出递推公式为 dp[j] += dp[j-coins[i]]
实现
class Solution { public int change(int amount, int[] coins) { //递推表达式 int[] dp = new int[amount + 1]; //初始化dp数组，表示金额为0时只有一种情况，也就是什么都不装 dp[0] = 1; for (int i = 0; i < coins.length; i++) { for (int j = coins[i]; j <= amount; j++) { dp[j] += dp[j - coins[i]]; } } return dp[amount]; } }
