coin_change2.py

from functools import lru_cache

class Solution:
    def change(self, amount: int, coins: List[int]) -> int:
        
        @lru_cache
        def dfs(amt): 
            if amt == 0: return 1
            if amt < 0: return 0
            return sum(dfs(amt - coins[i]) for i in range(len(coins)))
        
        return dfs(amount)