The Coin Change Problem
The Coin Change Problem
+ 0 comments Here is Python solution:
def getWays(n, c): # Write your code here dp = [0] * (n+1) dp[0] = 1 for i in range(m): for j in range(c[i], n+1): dp[j] += dp[j-c[i]] return dp[n]
+ 0 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));
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
return dp[c.length][n];
}
+ 0 comments JAVA SOLUTION
long[][] dp = new long[c.size()+1][n+1]; int m = c.size(); for(int j=0;j<=n;j++){ dp[0][j] = 0; } for(int i=0;i<=m;i++){ dp[i][0] = 1; } for(int i=1;i<=m;i++) { for(int j=1;j<=n;j++) { if(c.get(i-1).intValue()>j){ dp[i][j] = dp[i-1][j]; } else{ dp[i][j] = dp[i-1][j] + dp[i][j-c.get(i-1).intValue()]; } } } return dp[m][n]; }
+ 0 comments Bottom up approach. First sort coins in ascending order. For each coin, we either take it or don't. If we don't take it, it is the value before. And if we take it, the i value must be greater than coin value and dp[i - coin] would have already been calculated so just add that.
long getWays(int n, vector<long> c) { std::vector<uint64_t> dp(n+1, 0); dp[0] = 1; std::sort(c.begin(), c.end()); for (auto coin : c) { for (auto i = 0; i <= n; ++i) { if (i >= coin) { dp[i] += dp[i - coin]; } } } return dp[n]; }
+ 0 comments Here is the solution of The Coin Change Problem Click Here
Sort 689 Discussions, By:
Please Login in order to post a comment