We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
After some tinkering, I finally got my JS solution Down:
function getWays(n, c) {
let dp = Array.from({length: c.length + 1}, () => Array(n+1).fill(0));
for (let i = 0; i < c.length + 1; i++){
dp[i][0] = 1;
}
for (let i = 1; i < c.length + 1; i++){
for (let j = 1; j < n + 1; j++){
if (j < c[i-1]){
dp[i][j] = dp[i-1][j];
} else {
dp[i][j] = dp[i-1][j] + dp[i][j - c[i-1]];
}
}
}
Logically, we initialize a dp table with n + 1 columns and c.length (the number of coins) + 1 rows. In each row, we consider only having that coin and all coins from the rows above. For each j value (as we iterate up till n.length + 1, we consider the different ways to make "j" in change. There are two options:
1. j is smaller than the coin we are consider in this row (or c[i-1])
* In this case, the amount of ways to make change with this coin, is the same as the number of ways to make change before now (without this coin), or d[i][j] = d[i-1][j]
3. j is equal to or greater than our current coin being consider (c[i-1])
* In this case, the number of ways to make change is the sum of
* The number of ways to make change for this amount WITHOUT this coin (d[i-1][j])
* The number of ways to make change for j - c[i-1] on the current row (and including the current coin.
Hope this helps some other Javascript users out there! Happy hacking
The Coin Change Problem
You are viewing a single comment's thread. Return to all comments →
**JS Solution Below! **
After some tinkering, I finally got my JS solution Down: function getWays(n, c) { let dp = Array.from({length: c.length + 1}, () => Array(n+1).fill(0));
1. j is smaller than the coin we are consider in this row (or c[i-1]) * In this case, the amount of ways to make change with this coin, is the same as the number of ways to make change before now (without this coin), or d[i][j] = d[i-1][j] 3. j is equal to or greater than our current coin being consider (c[i-1]) * In this case, the number of ways to make change is the sum of * The number of ways to make change for this amount WITHOUT this coin (d[i-1][j]) * The number of ways to make change for j - c[i-1] on the current row (and including the current coin.
Hope this helps some other Javascript users out there! Happy hacking
}