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] 。按照上述的推导公式就可以得出。
实现
代码语言：javascript复制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 {
public int lastStoneWeightII(int[] stones) {
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 - dp[target] - dp[target];
}
}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 <= 200 <= nums[i] <= 10000 <= 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的 。所以是不存在的。
实现
代码语言：javascript复制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三层， 第一层循环数组中的内容， 后面两层循环背包。
实现
代码语言：javascript复制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]]
实现
代码语言：javascript复制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];
}
}
