DP - Top Down1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19class Solution {
private int coinChangeUtil(int[] coins,int rem,int[] count){
if(rem<0) return -1;
if(rem==0) return 0;
if(count[rem-1]!=0) return count[rem-1];
int min=Integer.MAX_VALUE;
for(int coin:coins){
int res=coinChangeUtil(coins,rem-coin,count);
if(res>=0&&res<min) min=res+1;
}
count[rem-1]=min==Integer.MAX_VALUE?-1:min;
return count[rem-1];
}
public int coinChange(int[] coins, int amount) {
if(amount<1) return 0;
return coinChangeUtil(coins,amount,new int[amount]);
}
}