509. 斐波那契数

这个题目根据题意，暴力解法就是一个简单的递归，求$fib(n)$的值，我们求$fib(n-1)+fib(n-2)$就可以了。当n是0,1,2的时候就是fib函数的一个基础状态。终止递归的条件。但是这个效率很低，时间复杂度是$O(2^n)$。

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(4)$和$fib(3)$,而$fib(4)$又需要求$fib(3)$和$fib(2)$，这里的$fib(3)$就重复计算了，包括其他的一些中间状态也有可能会被多次计算。那我们就可以做一个备忘录，要计算一个值，先看看之前是不是算过了，算过就不用重复算了，如果没有算过，就算一下，存到备忘录里面，然后再返回这个值。因为没有了重复计算，每个$fib(n)$都只需要计算一次就行了。时间复杂度直接从$O(2^n)$降低到了$O(n)$，提升非常的巨大。

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]

当然，上面是递归的写法，我们还可以使用一个简单的for循环通过迭代的写法来解决这个问题。递归是自顶向下，不断的分解问题，迭代是自底向上，从下面往上推出最终的结果。这样的话，我们连备忘录memo也可以进行优化了，我们只需要知道$fib(n-1)$和$fib(n-2)$的状态就可以了。使用两个变量，然后进行更新替换即可。

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,那我们求11-1=10,面额为10最少需要x枚硬币，求11-2=9,面额为9最少需要y枚硬币，求11-5=6,面额为6最小需要z枚金币，然后求max(x,y,z)的最小值，加上我们这次选择的硬币，就是最小值了。base case就是不停的往下凑，刚好能凑到0,那就是可以凑出来，如果凑的值小于0,那就是不符合条件了。最后再加上备忘录功能，如果一个金额，最小需要多少枚硬币凑齐已经算过，就不用重复计算了。这是递归的解法。

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]

会了递归，转换成迭代也就不难了,创建一个备忘录数组。外层for循环求的是dp数组，内层for循环是尝试不同的选择，然后更新dp[i]这个地方的答案。这里的dp数组默认值是amount+1就可以，结果肯定不会超过amount的。作为一个区分。

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]