算法训练营Day44(动态规划之完全背包 6)

说明

完全背包的理论基础

区别

思考

为什么? dp[0]=1 ，还有遍历顺序

class Solution:
    def change(self, amount: int, coins: List[int]) -> int:
        dp = [0]*(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[amount]

提醒

题目求的是排列?

class Solution:
    def combinationSum4(self, nums: List[int], target: int) -> int:
        dp = [0] * (target + 1)
        dp[0] = 1
        for i in range(1, target + 1):  # 遍历背包
            for j in range(len(nums)):  # 遍历物品
                if i - nums[j] >= 0:
                    dp[i] += dp[i - nums[j]]
        return dp[target]

拓展面试题

一次可以爬1或2步，问爬完n阶楼有几种方法

再问如果一次可以爬m步，问爬完n阶楼有几种方法

写出来后问你求的是排列数还是组合数，

这个遍历顺序可不可以颠倒呢，

如果颠倒求的是什么场景，不颠倒求的是什么场景

总结

对于非完全背包问题（问装满这个背包有多少种方法），此时我们要区分求的是组合数还是排列数

①如果是组合数其遍历顺序是先遍历物品再遍历背包

②如果是排列数其遍历顺序是先遍历背包再遍历物品