509. 斐波那契数

根据定义，求 fib(n)fib(n) 可以递归计算 fib(n−1)+fib(n−2)fib(n-1)+fib(n-2)。当 n 为 0、1、2 时直接返回对应结果，作为递归的终止条件。这个写法直观，但会重复计算许多状态，时间复杂度为 O(2n)O(2^n)。

Python
class Solution:
    def fib(self, n: int) -> int:
        if n == 0:
            return 0
        if n == 1:
            return 1
        if n == 2:
            return 1
        return self.fib(n - 1) + self.fib(n - 2)

例如求 fib(5)fib(5) 时，需要先求 fib(4)fib(4) 和 fib(3)fib(3)；而 fib(4)fib(4) 又要计算 fib(3)fib(3) 和 fib(2)fib(2)，其中 fib(3)fib(3) 被重复计算了。可以用备忘录保存结果：计算前先查是否已有记录，有就直接返回，没有再计算并保存。这样每个 fib(n)fib(n) 只需计算一次，时间复杂度从 O(2n)O(2^n) 降到 O(n)O(n)。

Python
class Solution:
    def fib(self, n: int) -> int:
        memo = [-1 for _ in range(n + 1)]
        return self.func(n, memo)

    def func(self, n, memo):
        if n == 0:
            return 0
        elif n == 1:
            return 1
        elif n == 2:
            return 1
        if memo[n] != -1:
            return memo[n]
        memo[n] = self.func(n - 1, memo) + self.func(n - 2, memo)
        return memo[n]

也可以改成迭代。递归自顶向下分解问题，迭代则从基础状态向上计算。由于下一个状态只依赖 fib(n−1)fib(n-1) 和 fib(n−2)fib(n-2)，不必保留整个备忘录数组，用两个变量记录前两项并依次更新即可。

Python
class Solution:
    def fib(self, n: int) -> int:
        if n < 2:
            return n
        fib_n_1 = 1
        fib_n_2 = 0
        fib_n = 0
        for i in range(2, n + 1):
            fib_n = fib_n_1 + fib_n_2
            fib_n_2 = fib_n_1
            fib_n_1 = fib_n
        return fib_n

322. 零钱兑换

这里把剩余金额 amount 作为状态，dp 函数返回凑出这个金额所需的最少硬币数。每次选择一枚硬币，剩余金额就减去它的面额。例如面额为 [1,2,5]，目标金额为 11，分别考虑剩余金额 10、9、6；若它们的最少硬币数为 x、y、z，就从可行结果中取最小值，再加上本次选择的 1 枚硬币。剩余金额为 0 时返回 0，小于 0 时表示这条路径不可行。最后用备忘录记录每个金额的答案，避免重复计算。

Python
class Solution:
    def __init__(self):
        self.memo = []

    def coinChange(self, coins: List[int], amount: int) -> int:
        self.memo = [-666] * (amount + 1)
        return self.dp(coins, amount)

    def dp(self, coins, amount):
        if amount == 0:
            return 0
        if amount < 0:
            return -1
        if self.memo[amount] != -666:
            return self.memo[amount]
        res = float("inf")
        for coin in coins:
            subProblem = self.dp(coins, amount - coin)
            if subProblem == -1:
                continue
            res = min(res, subProblem + 1)
        self.memo[amount] = res if res != float("inf") else -1
        return self.memo[amount]

迭代写法用 dp 数组保存各金额的答案：外层从小到大枚举金额 i，内层尝试每种硬币，更新 dp[i]。初始值设为 amount+1，用于表示尚不可达；因为硬币面额是正整数，只要能凑出 amount，使用的硬币数就不会超过 amount。dp[0] 则设为 0。

Python
class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        dp = [amount + 1] * (amount + 1)
        dp[0] = 0
        for i in range(len(dp)):
            for coin in coins:
                if i - coin < 0:
                    continue
                dp[i] = min(dp[i], 1 + dp[i - coin])
        return -1 if dp[amount] == amount + 1 else dp[amount]
谢谢你读到这里。 ✧