518. 零錢兌換 II文章來源：http://www.zghlxwxcb.cn/news/detail-709298.html
這道題其實就是一個完全背包問題，關(guān)于背包問題的相關(guān)文章見：文章來源地址http://www.zghlxwxcb.cn/news/detail-709298.html
- 01背包問題 – 動態(tài)規(guī)劃
- 完全背包問題
class CoinChange:
"""
完全背包
518. 零錢兌換 II
https://leetcode.cn/problems/coin-change-ii/
"""
def solution(self, amount: int, coins: List[int]) -> int:
n = len(coins)
# dp[i][j]: 若只使?前 i 個物品（可以重復(fù)使?），當(dāng)背包容量為 j 時，有 dp[i][j] 種?法可以裝滿背包。
dp = [[0 for _ in range(amount+1)] for _ in range(n+1)]
# base case
for i in range(n + 1):
dp[i][0] = 1
for i in range(1, n+1):
for j in range(1, amount+1):
if j - coins[i-1] >= 0:
dp[i][j] = dp[i-1][j] + dp[i][j-coins[i-1]]
else:
dp[i][j] = dp[i - 1][j]
return dp[n][amount]
def solution2(self, amount: int, coins: List[int]) -> int:
"""
空間壓縮，二維變一維
:param amount:
:param coins:
:return:
"""
n = len(coins)
# dp[j]: 當(dāng)背包容量為 j 時，有 dp[j] 種?法可以裝滿背包。
dp = [0 for _ in range(amount + 1)]
# base case
dp[0] = 1
for i in range(n):
# 這里只能從前往后正向遍歷，因為要考慮重復(fù)使用的情況，區(qū)別在于這里 dp[i][j-coins[i-1]]
# 當(dāng)使用了coins[i]這枚硬幣時，可重復(fù)多次使用，所以不是 dp[i-1][j-coins[i-1]]
# dp[i][j] = dp[i-1][j] + dp[i][j-coins[i-1]]
for j in range(1, amount + 1):
if j - coins[i] >= 0:
dp[j] = dp[j] + dp[j - coins[i]]
return dp[amount]
到了這里，關(guān)于518. 零錢兌換 II -- 完全背包的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
