壓抑與痛苦，那些輾轉反側的夜，終會讓我們更加強大

????????????????????????????????????????????????????????????????????????????????—— 25.5.16

一、遞推的概念

????????遞推 ——?遞推最通俗的理解就是數列，遞推和數列的關系就好比 算法 和 數據結構 的關系，數列有點像數據結構中的線性表(可以是順序表，也可以是鏈表，一般情況下是順序表)，而遞推就是一個循環或者迭代的枚舉過程，遞推本質上是數學問題。

---

二、509. 斐波那契數

斐波那契數?（通常用?F(n)?表示）形成的序列稱為?斐波那契數列?。該數列由?0?和?1?開始，后面的每一項數字都是前面兩項數字的和。也就是：

F(0) = 0，F(1)?= 1
F(n) = F(n - 1) + F(n - 2)，其中 n > 1

給定?n?，請計算?F(n)?。

示例 1：

輸入：n = 2
輸出：1
解釋：F(2) = F(1) + F(0) = 1 + 0 = 1

示例 2：

輸入：n = 3
輸出：2
解釋：F(3) = F(2) + F(1) = 1 + 1 = 2

示例 3：

輸入：n = 4
輸出：3
解釋：F(4) = F(3) + F(2) = 2 + 1 = 3

方法一 遞歸

① 終止條件

當?n == 0?時，直接返回?0（對應斐波那契數列的第 0 項）。

當?n == 1?時，直接返回?1（對應斐波那契數列的第 1 項）。

② 遞歸計算

當?n > 1?時，當前項的值為前兩項之和：fib(n) = fib(n-1) + fib(n-2)。

遞歸調用自身計算?fib(n-1)?和?fib(n-2)，并返回它們的和。

    def fib(self, n: int) -> int:if n == 0:return 0elif n == 1:return 1else:return self.fib(n -2) + self.fib(n - 1)

方法二 迭代

① 初始化結果列表

創建列表?res，初始值為?[0, 1]，對應斐波那契數列的前兩項。

② 循環填充中間項

循環范圍：i?從 2 到?n-1（不包含?n）。

遞推公式：每次將?res[i-1]?和?res[i-2]?的和添加到?res?中。

返回結果：返回?res[n]，即列表的第?n?項（索引為?n）。

    def fib(self, n: int) -> int:res = [0, 1]for i in range(2, n + 1):res.append(res[i - 1] + res[i - 2])return res[n]                            

---

三、1137. 第 N 個泰波那契數

泰波那契序列?Tn?定義如下：?

T0?= 0, T1?= 1, T2?= 1, 且在 n >= 0?的條件下 Tn+3?= Tn?+ Tn+1?+ Tn+2

給你整數?n，請返回第 n 個泰波那契數?Tn?的值。

示例 1：

輸入：n = 4
輸出：4
解釋：
T_3 = 0 + 1 + 1 = 2
T_4 = 1 + 1 + 2 = 4

示例 2：

輸入：n = 25
輸出：1389537

方法一 遞歸

① 終止條件

當?n == 0?時，直接返回?0（對應斐波那契數列的第 0 項）。

當?n == 1?時，直接返回?1（對應斐波那契數列的第 1 項）。

當?n == 2?時，直接返回?1（對應斐波那契數列的第 2?項）。

② 遞歸計算

當?n > 1?時，當前項的值為前三項之和：fib(n) = fib(n-1) + fib(n-2) + fib(n-3)。

遞歸調用自身計算?fib(n-1)?和?fib(n-2)和fib(n-3)，并返回它們的和。

class Solution:def tribonacci(self, n: int) -> int:if n == 0:return 0elif n == 1 or n == 2:return 1else:return self.tribonacci(n - 1) + self.tribonacci(n - 2) + self.tribonacci(n - 3)

方法二 迭代

① 初始化結果列表

創建列表?res，初始值為?[0, 1, 1]，對應斐波那契數列的前三項。

② 循環填充中間項

循環范圍：i?從 3?到?n + 1。

遞推公式：每次將?res[i-1]?和?res[i-2] 和 res[i-3]?的和添加到?res?中。

返回結果：返回?res[n]，即列表的第?n?項（索引為?n）。

class Solution:def tribonacci(self, n: int) -> int:res = [0, 1, 1]for i in range(3, n + 1):res.append(res[i - 3] + res[i - 2] + res[i - 1])return res[n]

---

四、斐波那契數列變形 爬樓梯問題

假設你正在爬樓梯。需要?n?階你才能到達樓頂。

每次你可以爬?1?或?2?個臺階。你有多少種不同的方法可以爬到樓頂呢？

示例 1：

輸入：n = 2
輸出：2
解釋：有兩種方法可以爬到樓頂。
1. 1 階 + 1 階
2. 2 階

示例 2：

輸入：n = 3
輸出：3
解釋：有三種方法可以爬到樓頂。
1. 1 階 + 1 階 + 1 階
2. 1 階 + 2 階
3. 2 階 + 1 階

方法一 遞歸?

思路與算法

① 終止條件

當?n == 1?時，只有?1 種爬法（一步）。當?n == 2?時，有?2 種爬法（一步一步或直接兩步）。

② 遞歸分解

當?n > 2?時，最后一步可能是從?n-1?級跨一步到達，或從?n-2?級跨兩步到達。

因此，總爬法數為前兩級的爬法數之和：climbStairs(n) = climbStairs(n-1) + climbStairs(n-2)。

class Solution:def climbStairs(self, n: int) -> int:if n == 1:return 1elif n == 2:return 2else:return self.climbStairs(n - 1) + self.climbStairs(n - 2)

方法二 迭代

思路與算法

① 初始化結果列表

創建列表?res，初始值為?[1, 1]，分別對應?n=0?和?n=1?的爬法數。注意：此處?res[0]=1?是為了后續計算方便，實際題目中?n ≥ 1，因此?res[0]?不會被直接使用。

② 循環填充結果列表

循環范圍：i?從 2 到?n（包含?n）。

遞推公式：對于每個?i，計算?res[i] = res[i-1] + res[i-2]，即前兩級的爬法數之和。

返回結果：返回?res[n]，即第?n?級樓梯的爬法數。

class Solution:def climbStairs(self, n: int) -> int:res = [1, 1]for i in range(2, n + 1):res.append(res[i - 1] + res[i - 2])return res[n]

---

五、二維遞推問題

? ? ? ? 像斐波那契數列這種問題，是一個一維數組來解決的，有時候一維數組解決不了的問題我們應該升高一個維度看

? ? ? ? 長度為 n(1 ≤ n < 40)的只由“A"、"C"、"M"三種字符組成的字符串，可以只有其中一種或兩種字符，但絕對不能有其他字符，且禁止出現 M 相鄰的情況，問這樣的串有多少種？??? ?

思路與算法

① 邊界條件處理

當?n = 0?時，直接返回 0（空字符串）。

② 狀態定義

dp[i][0]：長度為?i?且最后一個字符是?M?的字符串數目。

dp[i][1]：長度為?i?且最后一個字符不是?M（即?A?或?C）的字符串數目。

Ⅰ、初始化

當?i = 1?時：dp[1][0] = 1（字符串為?M）。dp[1][1] = 2（字符串為?A?或?C）。

Ⅱ、狀態轉移（循環?i?從 2 到?n）

計算?dp[i][0]（末尾為?M）：前一個字符不能是?M（否則相鄰），因此只能從?dp[i-1][1]?轉移而來。遞推式：dp[i][0] = dp[i-1][1]。

計算?dp[i][1]（末尾為非?M）：前一個字符可以是?M?或非?M（即?dp[i-1][0] + dp[i-1][1]）。當前字符有 2 種選擇（A?或?C），因此總數乘以 2。遞推式：dp[i][1] = (dp[i-1][0] + dp[i-1][1]) * 2。

Ⅲ、結果計算

最終結果為長度為?n?的所有合法字符串數目，即?dp[n][0] + dp[n][1]。

def count_valid_strings(n: int) -> int:if n == 0:return 0# dp[i][0]: 長度為i且最后一個字符是M的字符串數目# dp[i][1]: 長度為i且最后一個字符不是M的字符串數目dp = [[0, 0] for _ in range(n + 1)]dp[1][0] = 1  # Mdp[1][1] = 2  # A, Cfor i in range(2, n + 1):dp[i][0] = dp[i-1][1]  # 前一個字符不能是Mdp[i][1] = (dp[i-1][0] + dp[i-1][1]) * 2  # 前一個字符任意，當前選A/Creturn dp[n][0] + dp[n][1]

---

六、119. 楊輝三角 II

給定一個非負索引?rowIndex，返回「楊輝三角」的第?rowIndex?行。

在「楊輝三角」中，每個數是它左上方和右上方的數的和。

示例 1:

輸入: rowIndex = 3
輸出: [1,3,3,1]

示例 2:

輸入: rowIndex = 0
輸出: [1]

示例 3:

輸入: rowIndex = 1
輸出: [1,1]

提示:

• 0 <= rowIndex <= 33

進階：

你可以優化你的算法到?O(rowIndex)?空間復雜度嗎？

思路與算法

① 初始化結果列表

創建空列表?resRows，用于存儲楊輝三角的每一行。

② 逐行生成楊輝三角

Ⅰ、外層循環（i?從 0 到?rowIndex）

對于每一行?i，創建空列表?resCols?用于存儲當前行的元素。

Ⅱ、內層循環（j?從 0 到?i）：

邊界條件：當?j?是當前行的第一個或最后一個元素時（即?j == 0?或?j == i），直接添加?1。

遞推關系：否則，當前元素的值為上一行的?j-1?和?j?位置元素之和（即?resRows[i-1][j-1] + resRows[i-1][j]）。將當前行?resCols?添加到?resRows?中。

返回指定行：循環結束后，返回?resRows?中的第?rowIndex?行。

class Solution:def getRow(self, rowIndex: int) -> List[int]:resRows = []for i in range(rowIndex + 1):resCols = []for j in range(i + 1):if j == 0 or j == i:resCols.append(1)# f[i][j] = f[i - 1][j - 1] + f[i - 1][j]else:resCols.append(resRows[i - 1][j] + resRows[i - 1][j - 1])resRows.append(resCols)return resRows[rowIndex]

---

七、119. 楊輝三角 II?空間優化

給定一個非負索引?rowIndex，返回「楊輝三角」的第?rowIndex?行。

在「楊輝三角」中，每個數是它左上方和右上方的數的和。

示例 1:

輸入: rowIndex = 3
輸出: [1,3,3,1]

示例 2:

輸入: rowIndex = 0
輸出: [1]

示例 3:

輸入: rowIndex = 1
輸出: [1,1]

提示:

• 0 <= rowIndex <= 33

進階：

你可以優化你的算法到?O(rowIndex)?空間復雜度嗎？

算法與思路

① 初始化二維數組?f

創建一個 2 行、rowIndex+1?列的二維數組?f，用于存儲中間結果。初始化?pre = 0?和?now = 1，分別表示當前行和前一行的索引。

② 設置初始條件

f[pre][0] = 1，對應楊輝三角的第一行?[1]。

③ 逐行生成楊輝三角

Ⅰ、外層循環（i?從 0 到?rowIndex）

遍歷每一行，生成當前行的元素。

Ⅱ、內層循環（j?從 0 到?i）

邊界條件：當?j?是當前行的第一個或最后一個元素時，設為?1。

遞推關系：否則，當前元素的值為前一行的?j?和?j-1?位置元素之和（即?f[pre][j] + f[pre][j-1]）。更新?pre?和?now?的值，交換當前行和前一行的角色。

返回結果：循環結束后，pre?指向的行即為所求的第?rowIndex?行，返回?f[pre]。

class Solution:def getRow(self, rowIndex: int) -> List[int]:f = []for i in range(0, 2):l = []for j in range(rowIndex + 1):l.append(0)f.append(l)pre = 0now = 1f[pre][0] = 1for i in range(0, rowIndex + 1):l = []for j in range(i + 1):if j == 0 or j == i:f[now][j] = 1else:f[now][j] = f[pre][j] + f[pre][j - 1]pre, now = now, prereturn f[pre]