DP #06. Coin Changing Minimum Coins. - mbhushan/dynpro GitHub Wiki
(6). Coin Changing Minimum Coins.
Given a total and coins of certain denomination with infinite supply, what is the
minimum number of coins it takes to form this total V.
int [] coins = {2, 3, 6, 7};
int V = 13;
Formula:
if (coins[i] >= j) {
T[i][j] = Min (T[i-1][j], T[i][j-coins[i]]+1)
} else {
T[i][j] = T[i-1][j]
}
OR
T[i] = Min(T[i], 1 + T[i - Coins[j]]
If we are maintaining one array to maintain min coin count and another array for
keeping track of parents.
refer here: coin change
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 2 | 0 | inf | 1 | inf | 2 | inf | 3 | inf | 4 | inf | 5 | inf | 6 | inf |
| 3 | 0 | inf | 1 | 1 | 2 | 2 | 2 | 3 | 3 | 3 | 4 | 4 | 4 | 5 |
| 6 | 0 | inf | 1 | 1 | 2 | 2 | 1 | 3 | 2 | 2 | 3 | 3 | 2 | 4 |
| 7 | 0 | inf | 1 | 1 | 2 | 2 | 1 | 1 | 2 | 2 | 2 | 3 | 2 | 2 |
- Time complexity - O(coins.size * total)
- Space complexity - O(coins.size * total)