解题思路

常见的背包问题有 1、组合问题。2、True、False 问题。3、最大最小问题。 以下题目整理来自大神 CyC，github 地址：github 我在大神整理的基础上，又做了细分的整理。分为三类。1、组合问题：377. 组合总和 Ⅳ494. 目标和518. 零钱兑换 II2、True、False 问题：139. 单词拆分416. 分割等和子集3、最大最小问题：474. 一和零322. 零钱兑换

组合问题公式

dp[i] += dp[i-num]

True、False 问题公式

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. 分析是否为背包问题。
2. 是以上三种背包问题中的哪一种。
3. 是 0-1 背包问题还是完全背包问题。也就是题目给的 nums 数组中的元素是否可以重复使用。
4. 如果是组合问题，是否需要考虑元素之间的顺序。需要考虑顺序有顺序的解法，不需要考虑顺序又有对应的解法。

背包问题具备的特征：给定一个 target，target 可以是数字也可以是字符串，再给定一个数组 nums，nums 中装的可能是数字，也可能是字符串，问：能否使用 nums 中的元素做各种排列组合得到 target。

1. 如果是 0-1 背包，即数组中的元素不可重复使用，nums 放在外循环，target 在内循环，且内循环倒序；

for num in nums:
    for i in range(target, nums-1, -1):

2. 如果是完全背包，即数组中的元素可重复使用，nums 放在外循环，target 在内循环。且内循环正序。

for num in nums:
    for i in range(nums, target+1):

3. 如果组合问题需考虑元素之间的顺序，需将 target 放在外循环，将 nums 放在内循环。

for i in range(1, target+1):
    for num in nums:

代码

class Solution:
    def combinationSum4(self, nums: List[int], target: int) -> int:
        if not nums:
            return 0
        dp = [0] * (target+1)
        dp[0] = 1
        for i in range(1,target+1):
            for num in nums:
                if i >= num:
                    dp[i] += dp[i-num]
        return dp[target]

https://leetcode-cn.com/problems/combination-sum-iv/solution/xi-wang-yong-yi-chong-gui-lu-gao-ding-bei-bao-wen-/