public class Solution {
int total = Integer.MAX_VALUE;
public int coinChange(int[] coins, int amount) {
if (amount == 0) return 0;
Arrays.sort(coins);
count(amount, coins.length1, coins, 0);
return total == Integer.MAX_VALUE?1:total;
}
void count(int amount, int index, int[] coins, int count){
if (index<0  count>=total1) return;
int c = amount/coins[index];
for (int i = c;i>=0;i){
int newCount = count + i;
int rem = amount  i*coins[index];
if (rem>0 && newCount<total)
count(rem, index1, coins, newCount);
else if (newCount<total)
total = newCount;
else if (newCount>=total1)
break;
}
}
}
Java recursive solution 3ms


Slightly modifed version, may be this one will make more sense.
public class Solution { int total = Integer.MAX_VALUE; public int coinChange(int[] coins, int amount) { Arrays.sort(coins); count(amount, coins.length1, coins, 0); return total == Integer.MAX_VALUE?1:total; } void count(int amount, int index, int[] coins, int count){ if (index>=0 && count<total1) for (int i = amount/coins[index];i>=0;i){ int rem = amount  i*coins[index]; int newCount = count + i; if (rem>0 && newCount<total) count(rem, index1, coins, newCount); else{ total = newCount<total?newCount:total; break; } } } } </code>

After taking a look at the problem again was able to bring down the running time from 45 ms down to 3 ms
public class Solution { int minCount = Integer.MAX_VALUE; public int coinChange(int[] coins, int amount) { Arrays.sort(coins); count(amount, coins.length1, coins, 0); return minCount == Integer.MAX_VALUE?1:minCount; } void count(int amount, int index, int[] coins, int count){ if (index<0  count+2>minCount) return; for (int i = amount/coins[index];i>=0;i){ int newAmount = amount  i*coins[index]; int newCount = count + i; if (newAmount>0 && newCount+1<minCount) count(newAmount, index1, coins, newCount); else{ if (newAmount==0 && newCount<minCount) minCount = newCount; break; } } } }

Fixed, btw online judge is failing this test. I don't think it's due to it being Integer.MAX_VALUE but due to it's use of DP which is way too slow.
public class Solution { long minCount = Long.MAX_VALUE; public int coinChange(int[] coins, int amount) { Arrays.sort(coins); count(amount, coins.length1, coins, 0); return minCount == Long.MAX_VALUE?1:(int)minCount; }

Good solution. Based on your solution I did some more optimization. It run even faster (2ms):
public class Solution { int minCount = Integer.MAX_VALUE; public int coinChange(int[] coins, int amount) { Arrays.sort(coins); count(amount, coins.length  1, coins, 0); return minCount == Integer.MAX_VALUE ? 1 : minCount; } void count(int amount, int index, int[] coins, int count) { if(amount % coins[index] == 0) { int newCount = count + amount / coins[index]; if(newCount < minCount) minCount = newCount; } if(index == 0) return; for (int i = amount / coins[index]; i >= 0; i) { int newAmount = amount  i * coins[index]; int newCount = count + i; int nextCoin = coins[index1]; if(newCount + (newAmount + nextCoin 1) / nextCoin >= minCount) break; count(newAmount, index  1, coins, newCount); } } }

public class Solution { static int minCount = 0; public int coinChange(int[] coins, int amount) { if(amount == 0) return 0; else if (amount >= Integer.MAX_VALUE) return 1; Arrays.sort(coins); count(coins,amount,coins.length1); return minCount; } private static void count(int[] coins, int amount, int index) { minCount+=amount/coins[index]; amount=amount%coins[index]; if(amount==0  index == 0) return; else count(coins,amount,index1); } }
For some strange reasons, this is NOT passing the validator. I have tried as much as possible to write the least minimum code to achieve the objective.

@sandiegosd I tried this:
if(newCount + newAmount / nextCoin >= minCount) break;
And the system gives an accept.
I'm also curious about why to use (newAmount + nextCoin 1).And I think the reason why this is much faster than the usual DPbottom up/top down is that:
We define
F(S)=F(S−C)+1
(F(S)  minimum number of coins needed to make change for amount S using coin denominations [ c0 … c(n−1) ]. )
And his solution is :
F[S] = F[S  C * i] + i (0<= i <= S/C)The 1st calculate every amount, and the 2nd only consider the possible amount.
And also he sorted the coins array, so we can break as soon as we know it's impossible to have a smaller counts.
