背包问题
| Title | 组合问题 | True、False问题 | 最大最小问题 |
|---|---|---|---|
| 题目 | 377. 组合总和 Ⅳ 494. 目标和 518. 零钱兑换 II |
139. 单词拆分 416. 分割等和子集 |
474. 一和零 322. 零钱兑换 |
| 公式 | dp[i] += dp[i-num] | dp[i] = dp[i] or dp[i-num] | dp[i] = min(dp[i], dp[i-num]+1)或者dp[i] = max(dp[i], dp[i-num]+1) |
步骤
1.分析是否为背包问题：给定一个target，target可以是数字也可以是字符串，再给定一个数组nums，nums中装的可能是数字，也可能是字符串，问：能否使用nums中的元素做各种排列组合得到target。
2.是以上三种背包问题中的哪一种。
3.是0-1背包问题还是完全背包问题。也就是题目给的nums数组中的元素是否可以重复使用。
4.如果是组合问题，是否需要考虑元素之间的顺序。需要考虑顺序有顺序的解法，不需要考虑顺序又有对应的解法。
技巧
1.如果是0-1背包，即数组中的元素不可重复使用，nums放在外循环，target在内循环，且内循环倒序；
for num in nums:
for i in range(target, nums-1, -1):
2.如果是完全背包，即数组中的元素可重复使用，不需要考虑元素之间顺序（数组内元素种类个数必须不同，如【1,2】和【2,1】相同），nums放在外循环，target在内循环。且内循环正序。
for num in nums:
for i in range(nums, target+1):
3.如果组合问题需考虑元素之间的顺序（数组内元素种类个数相同，但顺序可以不同，如【1,2】和【2,1】不同），需将target放在外循环，将nums放在内循环。
for i in range(1, target+1):
for num in nums: