problem322.py

'''

322. Coin Change
Medium

You are given coins of different denominations and a total amount of money amount. Write a function to compute the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.

Example 1:

Input: coins = [1, 2, 5], amount = 11
Output: 3 
Explanation: 11 = 5 + 5 + 1

Example 2:

Input: coins = [2], amount = 3
Output: -1

Solution:
Classic dp, for each element, determine the min value after the current index substracting the 
coin value. If it is out of the boundary, simply set it to MAX.

Very classic, explained on class, stupid if did not recall.

Top-down solution.(Or is it?)
'''

class Solution(object):
    def coinChange(self, coins, amount):
        MAX = float('inf')
        dp = [0] + [MAX] * amount

        for i in xrange(1, amount + 1):
            dp[i] = min([dp[i - c] if i - c >= 0 else MAX for c in coins]) + 1

        return [dp[amount], -1][dp[amount] == MAX]

if __name__ == '__main__':
    coins = [1,2,5]
    print Solution().coinChange(coins,30)