LeetCode 322. Coin Change

Description:

You are given coins of different denominations and a total amount of money amount. Write a function to compute the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.

You may assume that you have an infinite number of each kind of coin.

Example 1:

Input: coins = [1,2,5], amount = 11
Output: 3
Explanation: 11 = 5 + 5 + 1

Example 2:

Input: coins = [2], amount = 3
Output: -1

Solution:

n = coins.length
m = amount
Time Complexity : O(n*m)
Space Complexity: O(m)

// Tabulation solution
// Create an array where array[i] = least number of coins to make i
var coinChange = function(coins, amount) {
    // Array to hold the number of coins needed to make each amount
    const dp = Array(amount+1).fill(Infinity);
    // To make 0 you would not use any coins
    dp[0] = 0;

    // Fill the array with number of coins to make each i amount
    for(let i = 1; i < dp.length; i++) {
        // Find coins that can make amount i
        for(let coin of coins) {
            // If a coin can make the current amount check if this coin
            // is used in the sequence that uses fewest number of coins 
            // to make this amount
            if(i-coin >= 0) dp[i] = Math.min(dp[i], dp[i-coin]+1);
        }
    }

    return dp[amount] === Infinity ? -1 : dp[amount];
};