The key idea is we update
dp[i] with previous best results we got. One thing to keep in mind is if the previous result
dp[i-x] == -1, it can not be used to update current
dp[i] hence we ignore it.
class Solution(object): def coinChange(self, coins, amount): """ :type coins: List[int] :type amount: int :rtype: int """ dp =  for i in range(1, amount+1): dp += [min([dp[i-x]+1 for x in coins if i-x>=0 and dp[i-x]>=0] or [-1])] return dp[-1]