Problem statement

https://binarysearch.com/problems/Making-Change-Trequel/

Solution

Equal to Leetcode 0518. Coin Change 2.

Complexity

Time and space complexities are O(amount * N).

Code

class Solution:
    def solve(self, coins, amount):
        N = len(coins)
        if N == 0: return int(N == amount)
        
        dp = [[0] * N for _ in range(amount + 1)]
        for i in range(N): dp[0][i] = 1
        
        for i,j in product(range(amount), range(N)):
            dp[i+1][j] = dp[i+1][j-1]
            if i+1 - coins[j] >= 0:
                dp[i+1][j] = (dp[i+1][j] + dp[i+1-coins[j]][j]) % (10**9 + 7)      
                    
        return dp[-1][-1]