**Solution**

**Coin Change** https://leetcode.com/problems/coin-change/?tab=Description

**Memoization**

- Sketch a recursion tree and add a cache to store intermediate results.

```
class Solution(object):
def helper(self, coins, amount, cache):
if amount == 0:
return 0
elif amount in cache:
return cache[amount]
cache[amount] = float('inf')
for c in coins:
if amount - c >= 0:
cache[amount] = min(cache[amount], self.helper(coins, amount-c, cache) + 1)
return cache[amount]
def coinChange(self, coins, amount):
"""
:type coins: List[int]
:type amount: int
:rtype: int
"""
if amount == 0:
return 0
elif min(coins) > amount:
return -1
else:
coins.sort(reverse=True)
answer = self.helper(coins, amount, {})
return answer if answer != float('inf') else -1
```

**Dynamic Programming**

```
class Solution(object):
def coinChange(self, coins, amount):
"""
:type coins: List[int]
:type amount: int
:rtype: int
"""
MAX = amount + 1
coins.sort(reverse=True)
dp = [MAX]*(MAX)
dp[0] = 0
for i in xrange(1, MAX):
dp[i] = min([dp[i-c] if i>=c else (MAX) for c in coins]) ### List Comprehension is faster
dp[i] = dp[i] + 1 if dp[i] != MAX else dp[i]
return -1 if (dp[-1] == MAX) else dp[-1]
```

**Breadth First Search**