Day 18: LeetCode 322. Coin Change

Tag: follow JohnTing's Day 17

Source:

https://leetcode.com/problems/coin-change/

1.题意:

coins = [1,2,5] 代表面额为1,2,5的硬币，
求组合的加总为amount的最小所需硬币数。

2.思路:

作法
- curValue:目前值 before reaching amount
- dp[curValue] = 所花硬币数
- dp[amount] 即答案

3.程序码:

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        dp = [amount+1]*(amount+1)
        dp[0] = 0
        # max = amount(all consist of 1)+1
        '''
        ex: amount = 11 means 11's 1 if have coin 1
        To set max surely, we can plus 1.
        [12,...,12]
        
        ?: number of combination
        dp[0] = 0
        dp[1] = ?
        dp[2] = ??
        ...
        dp[amount] = ??...
        
        Run by actual value
        [1,2,5]
        dp[1] = 1 # 1x(1)=1
        dp[2] = dp[1]+1 or dp[2-2]+1 -- select minimum
        1) 1+1 (2)
        2) 2 (1) ... v 
        How to process no solution(return -1) ? 
        Ans: compare default value of dp and dp[amount]
        '''
        
        for i in range(1,amount+1):
            #print(i)
            for coin in coins:
                if i-coin>=0:
                    #print("In.")
                    dp[i] = min(dp[i-coin]+1,dp[i])
        return dp[amount] if dp[amount]!=(amount+1) else -1