题目浅析

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

  • 简单地说，就是给一堆不同数额的硬币和一个目标数字，求能用硬币凑出目标数字的组合数。

思路分享

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

  • 参考题解
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution:
    def change(self, amount: int, coins: List[int]) -> int:
        # 空间优化
        n = len(coins)
        f = [0]*(amount+1)
        f[0] = 1
        for i in range(n):
            for j in range(amount+1):
                if j >= coins[i]:
                    f[j] = f[j] + f[j-coins[i]]
                else:
                    f[j] = f[j]
        return f[amount]
        # 递推
        # f[i+1][j] = f[i][j] + f[i+1][j-coins[i]]
        n = len(coins)
        f = [[0]*(amount+1) for _ in range(n+1)]
        f[0][0] = 1
        for i in range(n):
            for j in range(amount+1):
                if j >= coins[i]:
                    f[i+1][j] = f[i][j] + f[i+1][j-coins[i]]
                else:
                    f[i+1][j] = f[i][j]
        # print(f)
        return f[n][amount]
        # 记忆化搜索
        sorted(coins)
        @cache
        def dfs(i:int, amount:int) -> int:
            if amount < 0:
                return 0
            if i == -1:
                return 1 if amount == 0 else 0
            return (dfs(i-1, amount) + dfs(i, amount-coins[i]))
        return dfs(len(coins)-1, amount)