LeetCode: https://leetcode.com/problems/coin-change-2/
Description:
You are given coins of different denominations and a total amount of money. Write a function to compute the number of combinations that make up that amount. You may assume that you have infinite number of each kind of coin.
Example 1:
Input: amount = 5, coins = [1, 2, 5]
Output: 4
Explanation: there are four ways to make up the amount:
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1
Example 2:
Input: amount = 3, coins = [2]
Output: 0
Explanation: the amount of 3 cannot be made up just with coins of 2.
Solution:
n = coins.length
m = amount
Time Complexity: O(n*m)
Space Complexity: O(m)
// We will be using tabulation in this solution.
// Create a table (rows: (0 -> number of coins) x columns: (0 -> amount))
// rows -> coins we can use
// columns -> amount we want to make
// cells -> total number of ways we can make the amount
var change = function(amount, coins) {
// Create a table using a 2D array to store possible ways to make the amount
// Inititate every cell to 0
let dp = new Array(coins.length + 1).fill(0).map(()=>new Array(amount + 1).fill(0));
// The first row in our table handles the case of using 0 coins to make a certain amount
// There is only way to make an amount of 0 when using 0 coins
dp[0][0] = 1;
// Loop through all the rows in the table
for (let rowIndex=1;rowIndex<dp.length;rowIndex++) {
// There is 1 way to make an amount of 0 with any coin (which is to not use it)
dp[rowIndex][0] = 1;
// Loop through all columns in the row and find the total number of ways to make each amount
for (let currentAmount=1; currentAmount<dp[0].length; currentAmount++) {
// We build off of previous solutions by adding all the previous ways we
// made the current amount by looking at the cell located in the row above
// our current cell [rowIndex-1] and in the same column [currentAmount]
dp[rowIndex][currentAmount] = dp[rowIndex-1][currentAmount];
// Is the coin we are currently looking is less than the current amount?
// If it is then we will use the solution from a previous cell in the row of this coin
// and add it to the current cell
if (coins[rowIndex-1] <= currentAmount) {
// Subtract the current coin from the current amount
// Go to the cell in the row at [current amount - current coin]
// Add the total number of ways in this cell to our current cell
dp[rowIndex][currentAmount]+= dp[rowIndex][currentAmount-coins[rowIndex-1]];
}
}
}
return dp[coins.length][amount];
};
Top comments (0)