背包问题的套路
最近跟着代码随想录学到了线性规划章节，背包问题也是很常见的题型，在此总结一些做题套路。
常见的背包问题有：
-
组合问题
-
True, False问题
-
最大最小问题。
一、组合问题：
- 377. 组合总和 Ⅳ
- 494. 目标和
- 518. 零钱兑换 II
二、True, False问题：
- 139. 单词拆分
- 416. 分割等和子集
三、最大最小问题：
- 474. 一和零
- 322. 零钱兑换
组合问题公式
dp[i] += dp[i - num]
True, False问题公式
dp[i] = dp[i] || dp[i - num]
最大最小问题公式
dp[i] = max(dp[i], dp[i - num] + 1)
dp[i] = min(dp[i], dp[i - num] + 1)
以上三组公式是解决对应问题的核心公式。
当然拿到问题后，需要做到以下几个步骤：
-
分析是否为背包问题。
-
是以上三种背包问题中的哪一种。
-
是0-1背包问题还是完全背包问题。也就是题目给的 nums 数组中的元素是否可以重复使用。
-
如果是组合问题，是否需要考虑元素之间的顺序。需要考虑顺序有顺序的解法，不需要考虑顺序又有对应的解法。
背包问题的判定
背包问题具备的特征：给定一个 target，target 可以是数字也可以是字符串，再给定一个数组 nums，nums 中装的可能是数字，也可能是字符串，问：能否使用 nums 中的元素做各种排列组合得到 target
背包问题技巧：
1.如果是 0-1 背包，即数组中的元素不可重复使用，nums 放在外循环，target 在内循环，且内循环倒序；
for (int num : nums)
for (int i = target; i >= num; i--)
2.如果是完全背包，即数组中的元素可重复使用，nums 放在外循环，target 在内循环。且内循环正序。
for (int num : nums)
for (int i = 1; i <= target; i++)
3.如果组合问题需考虑元素之间的顺序，需将 target 放在外循环，将 nums 放在内循环。
for (int i = 1; i <= target; i++)
for (int num : nums)