题目浅析

  • 想查看原题可以点击题目链接。

  • 简单地说，就是给一些数额的零钱，每种数额数量无限，再给一个目标值，求用零钱凑到目标值所用最少的硬币数目。

思路分享

代码解答（强烈建议自行解答后再看）

  • 参考题解
1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        # 记忆化搜索
        sorted(coins)
        n = len(coins)
        @cache
        def dfs(i:int, a:int) -> int:
            if i == -1:
                return 0 if a==0 else inf
            return min(dfs(i-1, a), dfs(i, a-coins[i]) + 1 if a >= coins[i] else inf)
        return dfs(n-1, amount) if dfs(n-1, amount) != inf else -1