零钱兑换

2025/10/16

思路：贪心法，先找最大面额凑，再找次之的

评价：不对！面额有问题，只挑最大的可能凑不出来

推荐思路：动态规划，转移方程的step和面额有关系：

minCoin[amount] = min (coin coins, if amount-coin > 0 )(minCoin[amount-coin]) + 1

这是道经典的DP题，不应该不会

2025/10/19

def coinChange(self, coins: List[int], amount: int) -> int:
    min_coins = [-1] * amount
    for coin in coins:
        min_coins[coin] = 1
    for a in range(1, amount + 1):
        min_coins[a] = float('inf')
        for coin in coins:
            if a > coin and min_coins[a-coin] + 1 < min_coins[a]:
                min_coins[a] = min_coins[a-coin] + 1
            
    return min_coins[amount]