题解 | #兑换零钱(一)#

兑换零钱，动态规划，不同的初始状态

i元可以不加当前一枚硬币凑成dp[i]，也可以加当前一枚硬币凑成dp[i-coin]+1。
所以新状态需要综合dp[i]和dp[i-coin]+1。
如果表达式不相同，原因在于dp初始化方式不同。

class Solution:
    def minMoney(self , arr: List[int], aim: int) -> int:
        if not aim: return 0
        dp = [0]*(aim+1)      # aim+1维dp数组，dp[i]表示能凑成i元的最小硬币数，dp[0]=0
        for coin in arr:      # 用每种硬币更新状态
            dp[coin] = 1      # 用coin能凑coin元，最小需要1个，初始条件
            for i in range(coin+1, aim+1):
                if dp[i] and dp[i-coin]:             # 取和不取coin都能凑成i元，取最小
                    dp[i] = min(dp[i], dp[i-coin]+1)
                elif dp[i-coin]:                     # 不取coin凑不出i元，只能取
                    dp[i] = dp[i-coin]+1             # 其他，取coin凑不出i元，维持原状
        return dp[-1] if dp[-1] else -1