动态规划之背包问题总结（Java）

动态规划

动态规划的实质：根据前面的值能够推导出要求的这个，从而不断推导形成dp数组。需要分清楚：

1. 初始化；
2. dp数组推导
3. 遍历顺序

总结背包问题遍历顺序

1. 0-1背包问题中，先物品后背包 + 一维数组中倒序遍历
2. 完全背包中，如果无所谓顺序：先物品后背包 + 一维数组中正向遍历
3. 完全背包中，如果是组合问题需要考虑元素顺序：先背包后物品 + 一维数组中正向遍历

总结背包问题常见题型

1. 装满这个背包，能存放的最大价值/最小价值是多少？
   ans：使用滚动数组不断迭代，找出最后一个dp[n]；
   最大价值中要初始化都是0；最小价值值初始化大值
   eg:求最小价值 零钱兑换
   （1）物品可以被重复选：完全背包----内循环正序
   （2）无所谓顺序：最好就先物品再背包（习惯）
   注意：
   ①初始化–最大值，同时dp[0]=0；
   ②转移方程：dp[i] = Math.min(dp[i], 1 + dp[i - coins[j]]);
   ③最后注意检查结果（因为有初始化-可能不会有结果）
2. 怎么样分成两个相等子集/看两个子集差值最小/两个子集差值给出具体值？
   ans：使背包容量为sum/2，看物品能不能恰好装满。也是使用滚动数组不断迭代，因为设置了背包最大容量，所以不会超出，此外因为是恒向大的位置选择，所以可行。
3. 背包容量为n，在所有物品中有几种方案选择？
   ans：此时dp数组代表方案个数：如果当前物品不选择则依旧是dp[i - 1][j]，如果选择则是dp[i-1][j - num[i]];即：
   eg:求有几种方案 组合总数Ⅳ
   （1）物品可以被重复选：完全背包----内循环正序
   （2）顺序不同的序列被视作不同的组合：循环时外循环背包；内循环是物品
   注意：
   ①初始化：dp[0] = 1；
   ②转移方程
   

不要忘记初始化

4. 二维背包问题：找出二进制字符串数组中最多有5个0和3个1的最大长度。
   ans:使用二维数组，dp[i][j]：最多有i个0和j个1的strs的最大子集的大小为dp[i][j]。接着统计每个字符串中的0和1的个数，递推公式为：dp[p][q] = Math.max(dp[p][q], 1 + dp[p - a][q - b]); //长度只会增加1
5. 返回真假
   eg: 求ture/false 单词拆分
   想清楚这一阶段如果想为真，跟上一阶段有什么关系即可
   ①初始化：dp[0] = true；其他默认为false;