518. Coin Change 2

https://leetcode.com/problems/coin-change-2/

Python

Bottom Up DP

class Solution:
    def change(self, amount: int, coins: List[int]) -> int:
        dp = [0] * (amount+1)
        dp[0] = 1

        for coin in coins:
            for cur in range(coin, amount+1):
                dp[cur] += dp[cur-coin]

        return dp[amount]

JS

var change = function(amount, coins) {
    const dp = [...new Array(coins.length + 1)].map(() => new Array(amount + 1).fill(0));
    
    for (let j = 1; j <= coins.length; j++) {
        for (let i = 0; i <= amount; i++) {
            // base case 
            if (i === 0) dp[j][i] = 1;
            else {
                const coin = coins[j - 1];
                dp[j][i] = i - coin < 0 ? dp[j - 1][i] : dp[j][i - coin] + dp[j - 1][i];
            }
        }
    }
    // console.log(dp)
    return dp[coins.length][amount];
};

/**
[
  [ 0, 0, 0, 0, 0, 0 ],
  [ 1, 1, 1, 1, 1, 1 ],
  [ 1, 1, 2, 2, 3, 3 ],
  [ 1, 1, 2, 2, 3, 4 ]
]
 */