完全背包理论基础 每件物品都有无限个（也就是可以放入背包多次）dp

表示从下标为

0-i

的物品，每个物品可以取无限次，放进容量为j的背包，价值总和最大是多少递推公式：放物品和 不放物品，要取最大值。具体而言：对于物品1，不放的最大价值为60；放的最大价值为15【因为1可以多次放，dp

表示0,1物品取无限次，放入背包1的最大价值】

递推公式： dp

= max(dp

i - 1

, dp

j -

+

完全背包-一维数组：dp

= max(dp

, dp

j -

+

)，从前向后遍历 518. 零钱兑换 II

题目链接： 518. 零钱兑换 II - 力扣（）

思路 注意：题目中说的是组合数，那么

1,1,2

1,2,1

是相同的组合，属于重复情况，因为本题 中的所有值 互不相同，所以不需要我们去重。**二维dp数值 dp

：使用 下标为

0, i

的

能够凑满j这么大容量的包，有dp

种组合方法。一维dp数值，如果求组合数就是外层for循环遍历物品，内层for遍历背包。

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

代码

class Solution:
    def change(self, amount: int, coins: List[int]) -> int:
        dp = [[0]*(amount+1) for _ in range(len(coins)+1)]
        dp[0][0] = 1
        for i in range(1,len(coins)+1):
            for j in range(amount+1):
                if j<coins[i-1]:
                    dp[i][j] = dp[i-1][j]
                else:
                    dp[i][j] = dp[i-1][j]+dp[i][j-coins[i-1]]
        return dp[-1][-1]

一维数组

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

377. 组合总和 Ⅳ

题目链接： 377. 组合总和 Ⅳ- 力扣（）

思路 本题中顺序不同的序列被视作不同的组合【不懂原理】 代码

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

卡码网57. 爬楼梯

题目链接： 卡码网57. 爬楼梯 - 力扣（）

思路 完全背包问题，和377. 组合总和 Ⅳ类似 代码

def climbing_stairs(n,m):
    dp = [0]*(n+1)
    dp[0] = 1
    for j in range(n+1):
        for i in range(1,m+1):
            if j>=i:
                dp[j] += dp[j-i]
    return dp[-1]
n,m = list(map(int,input().split(' ')))
print(climbing_stairs(n,m))