(11). Coin Changing: number of ways to get total.
Given a value N, if we want to make change for N cents, and we have infinite
supply of each of S = { S1, S2, .. , Sm} valued coins, how many ways can we
make the change? The order of coins doesn’t matter.
For example,
for N = 4 and S = {1,2,3}, there are four solutions: {1,1,1,1},
{1,1,2},{2,2},{1,3}. So output should be 4.
For N = 10 and S = {2, 5, 3, 6},
there are five solutions: {2,2,2,2,2}, {2,2,3,3}, {2,2,6}, {2,3,5} and {5,5}.
So the output should be 5.
Example:
coins[] = {2, 3, 4, 5}
total = 10;
*** please refer below matrix for trace with DP formula.
Formula:
j <- column
coins(i) <- row
If (j >= coins[i]) {
T[i][j] = T[i-1][j] + T[i][j - coins[i]]);
} else {
T[i][j] = T[i-1][j]
}
|
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
|
| 2 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
|
| 3 |
1 |
0 |
1 |
1 |
1 |
1 |
2 |
1 |
2 |
2 |
2 |
|
| 4 |
1 |
0 |
1 |
1 |
2 |
1 |
3 |
2 |
4 |
3 |
5 |
|
| 5 |
1 |
0 |
1 |
1 |
2 |
2 |
3 |
3 |
5 |
5 |
7 |
<- Total Ways |
Coin Change
- Time Complexity: O(Total * len(coins))
- Space Complexity: O(Total * len(coins))