This solution is an optimized version based on qgambit2's solution https://leetcode.com/discuss/76307/java-recursive-solution-3ms.

```
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;
//return; // Not sure why return here will slow down in OJ. It's better in my local test however.
}
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[index-1];
if(newCount + (newAmount + nextCoin -1) / nextCoin >= minCount)
break;
count(newAmount, index - 1, coins, newCount);
}
}
}
```

It's a recursive version, but instead of taking out one coin in each level of the recursion , this solution will take care of one kind of coins in each recursion level, so the the maximum depth of the recursion will be coins.length, it's very shallow DSF. So no matter how big the amount is, it won't cause stack overflow.

For this particular solution, DP is not an ideal solution as it's not necessary to evaluate for all the previous amounts. Actually a very small portion of them is necessary.

The important optimization for this solution is to determine earliest time to stop the loop when we are sure no valid solutions are possible in further iteration.

```
if(newCount + (newAmount + nextCoin -1) / nextCoin >= minCount)
break;
```

This solution can run test case with extremely huge amount in less than 1ms without additional memory usage and stack overflow problem. For example: int[] coins = {7, 39, 83, 109, 901}; int amount = 1000000000;