I really like the use of max to reduce recursions. Just a tiny trick, but speed up from 26ms to 4ms on my computer. THANKS FOR SHARING~
Posts made by amber723
RE: 2ms beats 90% Java solution, a small trick to end search early
RE: Java recursive solution 3ms
@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 DP-bottom up/top down is that:
(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.
RE: Java 4ms Solution beats 99% inspired by 3 sum.
Maybe you can set
int closest = nums + nums + nums[len - 1];
int closest = Integer.MAX_VALUE;