0 0 vote
Article Rating
Subscribe
提醒
guest
1 评论
Newest
Oldest Most Voted
Inline Feedbacks
View all comments
暴走的楚狂

经典DP题目

#python
class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        dp = [float("inf")] * (amount + 1)
        dp[0] = 0                           

        for coin in coins:
            for next_amount in range(coin, amount + 1):
                dp[next_amount] = min(dp[next_amount], dp[next_amount - coin] + 1)

        return dp[-1] if dp[-1] != float("inf") else -1