My initial backtracking solution (not AC). Probably could've gotten it accepted if I added in memo.

```
def coinChange(self, coins, amount):
res = self.helper(coins, amount)
if res == sys.maxint:
return -1
return res
def helper(self, coins, amount):
res = sys.maxint
if amount == 0:
return 0
for denom in coins:
if amount - denom >= 0:
res = min(res, 1 + self.helper(coins, amount-denom))
return res
```

Then developed a DP solution (iterative)

```
def coinChange(self, coins, amount):
dp = [sys.maxint for i in range(amount+1)]
dp[0] = 0
for i in range(amount+1):
for denom in coins:
if i+denom < amount+1:
dp[i+denom] = min(dp[i+denom], dp[i] + 1)
# no solution since its infinity
if dp[-1] == sys.maxint:
return -1
return dp[-1]
```