完全背包问题
Method 1
class Solution:
def change(self, amount: int, coins: List[int]) -> int:
#dp[i][j] use the first i coins to achine amounts j
#TC: O(amount*len(coins))
#SC: O(amount*len(coins))
dp = [[0]*(amount + 1) for _ in range(len(coins)+1)]
for i in range(len(coins)+1):
dp[i][0] = 1
for i in range(len(coins)):
if coins[i] > amount:
return dp[i][-1]
for t in range(1, amount + 1):
if t - coins[i] < 0:
dp[i+1][t] = dp[i][t]
else:
dp[i+1][t] = dp[i][t] + dp[i+1][t-coins[i]]
print(dp)
return dp[-1][-1]
Method 1.5
class Solution:
def change(self, amount: int, coins: List[int]) -> int:
#dp[i][j] use the first i coins to achine amounts j
#TC: O(amount*len(coins))
#SC: O(amount)
dp = [0]*(amount + 1)
dp[0] = 1
for i in range(len(coins)):
if coins[i] > amount:
return dp[-1]
dp_prev = dp.copy()
for t in range(1, amount + 1):
if t - coins[i] < 0:
dp[t] = dp_prev[t]
else:
dp[t] = dp_prev[t] + dp[t-coins[i]]
return dp[-1]