-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathminimum-coins-dp.java
More file actions
98 lines (86 loc) · 3.33 KB
/
minimum-coins-dp.java
File metadata and controls
98 lines (86 loc) · 3.33 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
public class CoinChangingMinimumCoin {
/**
* Top down dynamic programing. Using map to store intermediate results.
* Returns Integer.MAX_VALUE if total cannot be formed with given coins
*/
public int minimumCoinTopDown(int total, int coins[], Map<Integer, Integer> map) {
//if total is 0 then there is nothing to do. return 0.
if ( total == 0 ) {
return 0;
}
//if map contains the result means we calculated it before. Lets return that value.
if ( map.containsKey(total) ) {
return map.get(total);
}
//iterate through all coins and see which one gives best result.
int min = Integer.MAX_VALUE;
for ( int i=0; i < coins.length; i++ ) {
//if value of coin is greater than total we are looking for just continue.
if( coins[i] > total ) {
continue;
}
//recurse with total - coins[i] as new total
int val = minimumCoinTopDown(total - coins[i], coins, map);
//if val we get from picking coins[i] as first coin for current total is less
// than value found so far make it minimum.
if( val < min ) {
min = val;
}
}
//if min is MAX_VAL dont change it. Just result it as is. Otherwise add 1 to it.
min = (min == Integer.MAX_VALUE ? min : min + 1);
//memoize the minimum for current total.
map.put(total, min);
return min;
}
/**
* Bottom up way of solving this problem.
* Keep input sorted. Otherwise temp[j-arr[i]) + 1 can become Integer.Max_value + 1 which
* can be very low negative number
* Returns Integer.MAX_VALUE - 1 if solution is not possible.
*/
public int minimumCoinBottomUp(int total, int coins[]){
int T[] = new int[total + 1];
int R[] = new int[total + 1];
T[0] = 0;
for(int i=1; i <= total; i++){
T[i] = Integer.MAX_VALUE-1;
R[i] = -1;
}
for(int j=0; j < coins.length; j++){
for(int i=1; i <= total; i++){
if(i >= coins[j]){
if (T[i - coins[j]] + 1 < T[i]) {
T[i] = 1 + T[i - coins[j]];
R[i] = j;
}
}
}
}
printCoinCombination(R, coins);
return T[total];
}
private void printCoinCombination(int R[], int coins[]) {
if (R[R.length - 1] == -1) {
System.out.print("No solution is possible");
return;
}
int start = R.length - 1;
System.out.print("Coins used to form total ");
while ( start != 0 ) {
int j = R[start];
System.out.print(coins[j] + " ");
start = start - coins[j];
}
System.out.print("\n");
}
public static void main ( String args[] ) {
int total = 13;
int coins[] = {7, 3, 2, 6};
CoinChangingMinimumCoin cc = new CoinChangingMinimumCoin();
Map<Integer, Integer> map = new HashMap<>();
int topDownValue = cc.minimumCoinTopDown(total, coins, map);
int bottomUpValue = cc.minimumCoinBottomUp(total, coins);
System.out.print(String.format("Bottom up and top down result %s %s", bottomUpValue, topDownValue));
}
}