背包问题：0-1背包问题、完全背包问题

一、0-1背包问题

物品不可以重复使用

使用二维dp时，内外循环顺序无所谓；使用一维dp时，外循环物品，内循环倒序循环背包容量。但二维dp可以优化成一维dp。

例题：DP41 【模板】01背包 待补充

二、完全背包问题

首先说明一下组合和排列。具体举例如下:

组合：[1,2,3]

排列：[1,2,3]、[1,3,2]、...

（一）、兑换零钱(一) 兑换零钱(一)_牛客题霸_牛客网 (nowcoder.com)

物品重复，非排列或组合问题，内外循环顺序无规定

class Solution:
    def minMoney(self , arr: List[int], aim: int) -> int:
        '''
        #从底向上
        #dp[i]组成i元的最小的货币数
        dp = [aim+1]*(aim+1)
        dp[0] = 0
        for coin in arr:
            for j in range(coin,aim+1):
                dp[j] = min(dp[j-coin]+1,dp[j])
        if dp[-1]!=aim+1:
            return dp[-1]
        else:
            return -1
        ''' 
        dp=[aim+1]*(aim+1)    #dp数组的定义：当目标金额为i时，至少需要dp[i]枚凑出
        dp[0]=0    # 金额为0时，结果则为0
        # aim=7  从金额1开始，凑金额1 2 3 4 5 6 7 ，每种金额需要的最少硬币数
        for i in range(1,aim+1):   
            # 遍历已有的金额面值 coins=[1,2,5]
            for coin in arr:
                diff=i-coin    #只有目标金额数大于等于已有的面值数 才能进行凑数  
                if diff>=0:
                    # 这里涉及到 状态转移方程式  金额数=某金额面值的张数y+dp[x]   
                    # 初dp[0]=0,其余dp[x]初已经始化为aim+1 但在求每种金额数需要的最少硬币数时，会将其最优值保存到相应的dp数组里
                    dp[i]=min(1+dp[diff],dp[i])
        # 如果aim可以整除arr中的任何一个数字，那货币数最多是aim，不可能是aim+1;若是aim+1,则说明都不能整除
        if dp[-1]!=aim+1:    
            return dp[aim]
        else:
            return -1

（二）、零钱兑换问题II 518. 零钱兑换 II - 力扣（LeetCode）

组合问题，外循环物品，内循环背包正序

class Solution:
    def change(self, amount: int, coins: List[int]) -> int:
        n = len(coins)
        #dp[i]表示可以凑成金额 i 的硬币组合数
        dp = [0]*(amount+1) #*背包容量+1
        dp[0] = 1
        for coin in coins:                  # 第一层循环：遍历硬币,这样硬币出现的次数唯一，例如coin=[1,2,3,5],这样1遍历完了以后，就不会再回来，不会有{1,3}和{3，1}这种情况 
            for i in range(coin, amount+1): # 第二层循环：遍历背包【正序】;从coin开始的原因是当第一层遍历物品遍历到coin时，此时背包的容量必须要大于coin才可以装下物品,故从coin开始。
                dp[i] += dp[i-coin]
        return dp[-1]

（三）、377. 组合总和Ⅳ 377. 组合总和 Ⅳ - 力扣（LeetCode）

排列问题。外循环背包，内循环物品正序

class Solution:
    def combinationSum4(self, nums: List[int], target: int) -> int:
        #dp[i]表示总和为 i 的元素组合的个数。
        dp = [0]*(target+1)
        #因为递推公式dp[i] += dp[i-j]的缘故，dp[0]要初始化为1，这样递归其他dp[i]的时候才会有数值基础。
        dp[0] = 1
        #先遍历背包
        for i in range(1,target+1):
            for j in nums:
                if i-j>=0:
                    dp[i] += dp[i-j]
        return dp[-1]