代码随想录算法训练营第三十七天｜（ 完全背包） 518. 零钱兑换 II 、 377. 组合总和 Ⅳ、70. 爬楼梯 （进阶）

完全背包问题和01背包问题的区别：

我们知道01背包内嵌的循环是从大到小遍历，为了保证每个物品仅被添加一次。而完全背包的物品是可以添加多次的，所以要从小到大去遍历。

完全背包问题实例：

def test_CompletePack():
    weight = [1, 3, 4]
    value = [15, 20, 30]
    bagWeight = 4
    
    dp = [0 for _ in range(bagWeight+1)]
    
    for i in range(len(weight)):
        for j in range(weight[i], bagWeight + 1):
            dp[j] = max(dp[j], dp[j - weight[i]] + value[i])
    
    return dp[-1]
            

518. 零钱兑换 II

class Solution:
    def change(self, amount: int, coins: List[int]) -> int:
        
        dp = [0 for _ in range(amount+1)]
        dp[0] = 1

        for i in range(len(coins)):
            for j in range(coins[i], amount + 1):
                dp[j] += dp[j - coins[i]]

        return dp[-1] 

377. 组合总和 Ⅳ

如果求组合数就是外层for循环遍历物品，内层for遍历背包。

如果求排列数就是外层for遍历背包，内层for循环遍历物品。

因为如果先遍历物品，那么3一定在1后面，就只有（1，3）这种组合，没有（3，1）这种组合了

class Solution:
    def combinationSum4(self, nums: List[int], target: int) -> int:
        dp = [0 for _ in range(target + 1)]

        dp[0] = 1

        for i in range(target + 1):
            for j in range(len(nums)):
                if i - nums[j] >= 0:
                    dp[i] += dp[i - nums[j]]
        
        return dp[-1]

57. 爬楼梯（进阶版）

def climbing_stairs(n,m):
    
    dp = [0 for _ in range(n + 1)]
    
    dp[0] = 1
    
    for i in range(n+1):
        for j in range(1, m + 1):  # (1 <= m < n)
            if i >= j:
                dp[i] += dp[i - j]
    
    return dp[-1]