It is a brilliant Solution!

While I am trying to understand it, some improvement ideas pop up.

Change 2 ** 31-1 to a smaller number

amount//coins[-1]+1

You are using 2**31-1 as the impossible answer. The maximum possible answer is that when you only use the smallest coin to get the amount which is amount//coins[-1], adding 1 on that gives us the boundary of all possible answer.

Another possible improvement is to have a pre-check in the outer for loop, if the shortest path (amount//coins[i]+1)is already longer than self.res, then we can break the for loop.

When the length of coin list is long, this improvement can contribute more.

I made a test with my PC, result shows 16% speed gain with 5000 times run each solution.

```
from timeit import timeit
class Solution(object):
def coinChange(self, coins, amount):
coins.sort(reverse = True)
lenc, self.res = len(coins), 2**31-1
def dfs(pt, rem, count):
if not rem:
self.res = min(self.res, count) ## Find an solution, compare the count with global count. Maybe refrese the global count.
for i in range(pt, lenc):
if coins[i] <= rem < coins[i] * (self.res-count): # if hope still exists
dfs(i, rem-coins[i], count+1)
for i in range(lenc):
dfs(i, amount, 0)
return self.res if self.res < 2**31-1 else -1
def coinChange2(self, coins, amount):
coins.sort(reverse = True)
lenc, self.res = len(coins), amount//coins[-1]+1
def dfs(pt, rem, count):
if not rem:
self.res = min(self.res, count) ## Find an solution, compare the count with global count. Maybe refrese the global count.
for i in range(pt, lenc):
if coins[i] <= rem < coins[i] * (self.res-count): # if hope still exists
dfs(i, rem-coins[i], count+1)
for i in range(lenc):
if self.res < (amount//coins[i]+1):
break
else:
dfs(i, amount, 0)
return self.res if self.res < amount//coins[-1]+1 else -1
print timeit('Solution().coinChange([186,419,83,408,32,31,29,28,27,26,25,24,23,22,21,20,19,18,17,16,15,13], 6249)', 'from __main__ import Solution', number = 5000)
print timeit('Solution().coinChange2([186,419,83,408,32,31,29,28,27,26,25,24,23,22,21,20,19,18,17,16,15,13], 6249)', 'from __main__ import Solution', number = 5000)
```

```
5.72996206357
4.76601419506
```