换钱的最少货币数

所以，F(S)的状态转移方程为

其中 C_j 代表的是第 j 枚货币的面值，即我们枚举最后一枚货币面额是C_j，那么F(S)需要从S-C_j这个金额对应的状态 F(S-C_j) 转移过来，再加上枚举的这枚货币数量1的贡献。由于题目是求货币的数量最少，所以 F(S)为前面能转移过来的状态的最小值。

假设 coins= [1, 2, 5]，amount = 11，即F(11) = min( F(10), F(9), F(6) ) + 1。

下面我们来看一下代码的实现。

import sys
class Solution:
    def coinChange(self, coins,amount):
        dp = [sys.maxsize] * (amount + 1)

        #S为0时，需要的货币数为0
        #S<0时，直接忽略dp[S]
        dp[0] = 0
        for coin in coins:
            #忽略S<0的。
            for x in range(coin, amount + 1):
                dp[x] = min(dp[x], dp[x - coin] + 1)
        return dp[amount] if dp[amount] != sys.maxsize else -1

该算法的时间复杂度是O(Sn)，其中S是金额数，n是不同面额的个数。空间复杂度是O(S)。