动态规划问题总结
一般背包问题有三类：
1、组合与排列组合
2、最多能放入多少值
3、装满背包有几种方法
4、背包装满最大价值(二维)
5、装满背包所有物品的最小个数
1.1.组合问题：
比如leetcode的第518题
给你一个整数数组 coins 表示不同面额的硬币，另给一个整数 amount 表示总金额。
请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额，返回 0 。
假设每一种面额的硬币有无限个。
问题特征：简而言之，就是给你一个数组num，里面装的是数字或者字符，给你一个数targe，可以是数字或者字符，计算出数组中能凑出值为target的个数
解析：看到个数，就是经典的组合问题，并且通过假设每一种面额的硬币有无限个这个信息，我们要使用完全背包而不是01背包来解决。
模板：如果是完全背包，即数组中的元素可重复使用，nums放在外循环，target在内循环。且内循环正序。
public int template1(int[] nums, int target)
{
int[] dp = new int[target+1];
int n = nums.length;
dp[0] = 1;
for (int i = 0; i < n; i++)
{
for (int j = nums[i];j <= target;j++)
{
dp[j] += dp[j-nums[i]];
}
}
return dp[target];
}1.2 排列组合问题
比如leetcode的第377题
给你一个由 不同 整数组成的数组
nums，和一个目标整数target。请你从nums中找出并返回总和为target的元素组合的个数。
示例：
输入：nums = [1,2,3], target = 4
输出：7
解释：
所有可能的组合为：
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)
请注意，顺序不同的序列被视作不同的组合。
解析：这里我们可以看出和组合问题有一个很明显的不同点， 顺序不同的序列被视作不同的组合，这就是组合排列问题，与元素组合的顺序相关
模板：
public int combinationSum4(int[] nums, int target)
{
Arrays.sort(nums);
int[] dp = new int[target+1];
dp[0] = 1;
int n = nums.length;
// 先遍历背包容量
for (int j = 1; j <= target; j++)
{
// 再遍历数组元素
for (int i = 0;i < n; i++)
{
if (nums[i] > j)
{
break;
}else
{
dp[j] += dp[j-nums[i]];
}
}
}
return dp[target];
}这里为什么先遍历背包容量，再遍历数组元素就能解决排列的问题呢
遍历顺序：如果按照往常这样计算的话，nums放在外循环，target在内循环
举一个例子：计算dp[4]的时候，结果集只有 {1,3} 这样的集合，不会有{3,1}这样的集合
为什么：举一个例子,nums = [1,2,3], target = 4
1:遍历nums（物品）放在外循环，遍历target的作为内循环
nums=1: dp[1] = 1,dp[2] = 1,dp[3] = 1,dp[4] = 1
nums=2: dp[2] = 2, dp[3] = 2, dp[4] = 3
nums=3: dp[3] = 3,dp[4] = 4
2:遍历target放在外循环，遍历nums（物品）作为内循环
j=1: dp[1] = 1
j=2: dp[2] = 1,dp[2] = 2
j=3: dp[3] = 2, dp[3] = 3, dp[3] = 4
j=4: dp[4] = 4,dp[4] = 6,dp[4] = 7
发现，在j=3，nums=2的时候，情况1的dp[3] = 2，情况2的dp[3] = 3
我们来看情况1:
nums=3,j=3时，dp[3] = dp[3] + (dp[0] + 3这种情况)
nums=2,j=3时，dp[3] = dp[3] + (dp[1] + 2这种情况)
nums=1,j=3时，dp[3] = dp[3] + (dp[2] + 1这种情况)=> dp[3] = 1不对
说明dp[2] 这里不应该等于1，应该等于2才对，这里dp[2] = 单选2，选两次1两种情况，
但是没考虑到单选2，因为nums=1，所以dp[3]少算了一种
但是如果遍历nums（物品）作为内循环，j=2的时候，dp[2] = 2，下一次j=3的时候，dp[2]成为了最终结果。
dp[3]用dp[2]的最终结果进行计算肯定是没问题的
总结，情况1的dp[3] += (dp[2]+1)这种情况的dp[2]不正确，没有用到dp[2]的最终结果，缺少了dp[2] += 单选2这种情况，说明上一层的dp[3]只有1 ，1 ，1这种情况，导致最后dp[4]结果不对
2、最多能放入多少值问题
比如leetcode的第416题
给你一个 只包含正整数 的 非空 数组
nums。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
示例1：
输入：nums = [1,5,11,5] 输出：true 解释：数组可以分割成 [1, 5, 5] 和 [11] 。
解析：
首先，本题要求集合nums里面能否出现总和为 sum / 2 的子集。也就是求集合nums里，背包容量sum / 2 ，nums中的元素最多能放入的值的总和。
如果dp[sum/2] == sum/2 说明，集合中的⼦集总和正好可以凑成sum/2，理解这⼀点很重要。
1.可以确定dp[i]的含义：容量为i时，nums中的元素最多能放入的值的总和,则i >= dp[i]
注意：物品i相当于元素i在nums数组的下标,value[i]=nums[i],weight[i]= nums[i]
3.递推公式变为dp[j] = max(dp[j],dp[j-nums[i]]+nums[i])
4.dp[i]数组初始化：dp[0] = 0，容量为0，什么都不能放，总和为0
5.遍历顺序问题，如果使用二维数组，当前行的值依赖于上一行的值，可以随意调整遍历顺序
如果使用一维数组，就需要物品顺序遍历，容量倒序遍历
倒序遍历是为了保证物品i只被放入一次。但如果一旦正序遍历了，那么物品0就会被重复加入多次！
举一个例子：物品0的重量weight[0] = 1，价值value[0] = 15
如果正序遍历
dp[1] = dp[1 - weight[0]] + value[0] = 15
dp[2] = dp[2 - weight[0]] + value[0] = 30
此时dp[2]就已经是30了，意味着物品0，被放入了两次，所以不能正序遍历。
为什么倒序遍历，就可以保证物品只放入一次呢？
倒序就是先算dp[2]
dp[2] = dp[2 - weight[0]] + value[0] = 15 （dp数组已经都初始化为0）
dp[1] = dp[1 - weight[0]] + value[0] = 15
所以从后往前循环，每次取得状态不会和之前取得状态重合，这样每种物品就只取一次了。
模板：
public boolean canPartition(int[] nums)
{
int n = nums.length;
int target = 0;
for (int i = 0; i < n; i++)
{
target += nums[i];
}
if (target % 2 != 0)
{
return false;
}else
{
target = target/2;
}
int[] dp = new int[target+1];
// 先遍历物品，也就是数组的值
for (int i = 0; i < n; i++)
{
// 再遍历背包容量,如果容量小于该物品重量，就不用遍历了
for (int j = target; j >= nums[i]; j--)
{
dp[j] = Math.max(dp[j],dp[j-nums[i]]+nums[i]);
}
}
return dp[target] == target;
}3、装满背包有几种方法
dp[j] += dp[j - nums[i]]，与1.1.组合问题相同，记住递推公式和遍历顺序即可
4、背包装满最大价值
比如leetcode的第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 。
解析：与最多能放入多少值类似，递推公式都是
dp[j] = max(dp[j], dp[j - nums[i]] + nums[i])
只不过nums[i]既是容量也是价值，如果nums[i]不对应，价值和容量，就演变成
dp[j] = max(dp[j], dp[j - weight[i]] + value[i])
但是物品价值可能不是一维的，题目可能演变成 两个不同类别的物品装满背包1容量为A，背包2容量为B的最大价值是多少，这时递推公式就演变成
dp[j][k] = max(dp[j][k],dp[j-weight[A]][k-weight[B]]+value[A]+value[B])
// 1.确定dp[j][k]的含义：最多有个j个0和k个1的strs的最大子集的大小为dp[j][k]
// 2.确定递推公式:
// dp[j][k] = max(dp[j][k],dp[j-当前字符串0的个数][k-当前字符串1的个数]+1)
// 3.dp[i]数组初始化：dp[0][0] = 0
// 4.确定遍历顺序：后向前遍历
public int findMaxForm1(String[] strs, int m, int n)
{
int[][] dp = new int[m+1][n+1];
int len = strs.length;
// 遍历物品
for (int i = 0; i < len; i++)
{
// 遍历容量，01背包，从后往前遍历
int zeroNum = searchZeroAndOneNum(strs[i])[0];
int oneNum = searchZeroAndOneNum(strs[i])[1];
for (int j = m; j >= zeroNum;j--)
{
for (int k = n; k >= oneNum;k--)
{
// 这里把物品装进背包的价值就是1
dp[j][k] = Math.max(dp[j][k],dp[j-zeroNum][k-oneNum]+1);
}
}
}
return dp[m][n];
}5、装满背包所有物品的最小个数
比如leetcode的322题：
给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。
你可以认为每种硬币的数量是无限的。
示例 1： 输入：coins = [1, 2, 5], amount = 11 输出：3 解释：11 = 5 + 5 + 1
示例 2： 输入：coins = [2], amount = 3 输出：-1
示例 3： 输入：coins = [1], amount = 0 输出：0
示例 4： 输入：coins = [1], amount = 1 输出：1
示例 5： 输入：coins = [1], amount = 2 输出：2
与 背包装满最大价值问题类似，只是变成了最小，dp数组的含义相应变化就可以了
// dp[j]: 在0-i这个硬币数组的范围内，凑足总额为j所需钱币的最少个数为dp[j]
// 递推公式：dp[j] = min(dp[j],dp[j-coins[i]]+1)
// 该层最小个数为上一层的最小个数，与
// 加入coins[i]这个硬币之后，dp[j-coins[i]]就是没加这个硬币，但是剩余容量刚好是coins[i]，能凑成j-coins[i]的最小个数，
// 返回这两者的最小值即可
public int coinChange(int[] coins, int amount)
{
int[] dp = new int[amount+1];
Arrays.fill(dp,Integer.MAX_VALUE);
dp[0] = 0;
int n = coins.length;
for (int i = 0; i < n; i++)
{
for (int j = coins[i];j <= amount;j++)
{
// 如果dp[j-coins[i]] = Integer.MAX_VALUE，说明j-coins[i]是无法凑成的，
// j是无法通过dp[j-coins[i]] + coins[i]凑成的
if (dp[j-coins[i]] != Integer.MAX_VALUE)
{
dp[j] = Math.min(dp[j],dp[j-coins[i]]+1);
}
}
}
return dp[amount] == Integer.MAX_VALUE ? -1 : dp[amount] ;
}