518.md

518 Coin Change 2

Description

link

---

Solution

• dp[j] += dp[j - i] for j in [i, amount] for i in coins
• 每来一个新的硬币，都可以使用j-i位置上的种类添加到当前位置，因为是新的硬币，所以不可能会重复

---

Code

Complexity T : O(n) M : O(n)

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