518. Coin Change 2
322. Coin Change 是找出最少硬幣的組合,這個題目是找出總共有幾種組合,其選擇的方式是類似的,就是要不斷的選擇,並且對目標減去選擇的硬幣的價值。
不過這裡有一個地方要優化,那就是對於目標值為 5
來說,選擇 [2, 2, 1], [2, 1, 2], [1, 2, 2]
都是一樣的情況。所以這時候可以針對此情況來優化,例如一開始就一直選小的硬幣,如果我開始選大的硬幣,我就要不斷地選更大的硬幣,策略性地去做選擇。
時間複雜度和上一題相同。
class Solution:
def change(self, amount: int, coins: List[int]) -> int:
ans = []
memo = {}
def helper(target, index):
if (target, index) in memo:
return memo[(target, index)]
if target < 0:
memo[(target, index)] = 0
elif target == 0:
memo[(target, index)] = 1
else:
count = 0
for i in range(index, len(coins)):
coin = coins[i]
count += helper(target - coin, i)
memo[(target, index)] = count
return memo[(target, index)]
return helper(amount, 0)
class Solution:
def change(self, amount: int, coins: List[int]) -> int:
dp = [0] * (amount + 1)
dp[0] = 1
for coin in coins:
for i in range(coin, amount + 1):
dp[i] += dp[i - coin]
return dp[amount]
Last updated