完全背包:

如果求組合數(shù): 外層for遍歷循環(huán)物品，內層for遍歷循環(huán)背包容量

如果求排列數(shù): 外層for遍歷循環(huán)背包容量， 內層for遍歷循環(huán)物品

步驟一、確定狀態(tài):

確定dp數(shù)組及下標含義

這里的dp是大小為amount的一維數(shù)組， dp[i]表示的是裝滿容量為i的背包， 有多少種裝法

步驟二、推斷狀態(tài)方程:

dp[j] += dp[j-coins[i]]

步驟三、規(guī)定初始條件:

初始條件:

全局初始化為0， dp[0]=1

步驟四、計算順序:

對于物品， 依然是正向遍歷，而對于背包，也是正向遍歷，因為這里的物品 可以取多次

class Solution:def change(self, amount: int, coins: List[int]) -> int:if amount == 0:return 1dp = [0] * (amount + 1)dp[0] = 1for i in range(len(coins)): # 遍歷物品for j in range(coins[i], amount+1): # 遍歷背包容量dp[j] += dp[j-coins[i]]return dp[amount]

?

總結

以上是生活随笔為你收集整理的98. Leetcode 518. 零钱兑换 II (动态规划-完全背包)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內容還不錯，歡迎將生活随笔推薦給好友。