518. Coin Change 2

Loading...LeetCode

如果Q322是bottom-up写的，那这个其实就是改一点点，然而我是top-down recursively写的...

其实但就coin change这个来说，bottom-up还好写一些，不需要去想状态转换方程，直接当作BFS/DFS来想就可以。

class Solution:
    def change(self, amount: int, coins: List[int]) -> int:
        dp = collections.defaultdict(int)
        dp[0] = 1
        
        for c in coins:
            for n in range(amount):
                dp[n+1] += dp[n+1-c]
        return dp[amount]