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]