動態規劃
遞歸知識要點
- 遞歸代碼模板：提供遞歸代碼的標準形式
public void recur(int level, int param)，包含終止條件（if (level> MAX_LEVEL)）、當前層邏輯處理（process(level, param)）、向下一層遞歸（recur(level: level +1, newParam)）以及狀態恢復（未完整代碼呈現，但為重要環節），強調對該模板的記憶有助于構建遞歸算法邏輯。 - 遞歸狀態樹：遞歸狀態樹展示了問題逐步分解為子問題再求解的層級結構，直觀呈現遞歸過程中各子問題間的關系，輔助理解遞歸算法的執行流程與問題處理機制。
- 人肉遞歸的問題及解決思路：人肉遞歸存在效率低、易出錯的問題，人腦記憶的局限性使得在處理多層遞歸（如第三、四層）時難度加大。解決方法是尋找最近最簡的方法，將問題拆解為可重復解決的子問題，運用數學歸納法思維，挖掘問題中的重復性，轉化為計算機指令解決，避免過度依賴人肉遞歸。
動態規劃知識要點
- 定義：動態規劃是一種數學優化方法和計算機編程方法，由Richard Bellman在20世紀50年代提出。其核心是通過遞歸方式把復雜問題分解為簡單子問題來簡化求解過程，具有“分治 + 最優子結構”的特點，在多個領域廣泛應用。
- 與遞歸、分治的關系：動態規劃與遞歸、分治既有共性又有差異。共性在于都要找出重復子問題；差異在于動態規劃具有最優子結構，并且在求解過程中能夠淘汰次優解，從而提高算法效率，普通遞歸或分治可能不具備這些特性。
- 實例分析：以
Fib(6)狀態樹為例，其中存在許多重復子狀態（如f(4)、f(3)、f(2)多次出現）。利用動態規劃淘汰次優解，可優化計算過程、避免重復計算，但可能使時間復雜度變為 n 2 n^2 n2，實際應用時需要權衡算法性能與復雜度。
題目練習
題目描述
使用動態規劃（Dynamic Programming）方法求解斐波那契數列（Fibonacci Sequence）的第 n 項。斐波那契數列的定義為：
F(0) = 0F(1) = 1F(n) = F(n-1) + F(n-2)（當n ≥ 2時）
分析思路
1. 動態規劃核心思想
斐波那契數列具有最優子結構和重疊子問題，適合用動態規劃求解：
- 最優子結構：
F(n)由F(n-1)和F(n-2)唯一確定。 - 重疊子問題：遞歸求解時，
F(n-1)和F(n-2)會被重復計算（如計算F(6)時，F(4)會被計算兩次）。動態規劃通過存儲中間結果避免重復計算，提升效率。
2. 狀態定義
定義 dp[i] 表示斐波那契數列的第 i 項的值。
3. 狀態轉移方程
根據斐波那契數列定義，狀態轉移方程為：
[ dp[i] = dp[i-1] + dp[i-2] ]
初始條件：
dp[0] = 0dp[1] = 1
4. 空間優化
常規動態規劃需用數組存儲所有中間狀態（空間復雜度 O(n)），但由于 dp[i] 僅依賴前兩項 dp[i-1] 和 dp[i-2]，可通過兩個變量 prev1（存儲 F(n-2)）和 prev2（存儲 F(n-1)）迭代更新，將空間復雜度優化至 O(1)。
最優解答（Python）
方法一：常規動態規劃（數組存儲中間狀態）
def fib(n: int) -> int:if n <= 1:return ndp = [0] * (n + 1)dp[0], dp[1] = 0, 1for i in range(2, n + 1):dp[i] = dp[i-1] + dp[i-2]return dp[n]
方法二：空間優化動態規劃（O(1) 空間）
def fib(n: int) -> int:if n <= 1:return nprev1, prev2 = 0, 1 # 對應 F(0) 和 F(1)for i in range(2, n + 1):current = prev1 + prev2 # 計算 F(i)prev1, prev2 = prev2, current # 迭代更新前兩項return prev2 # 最終 prev2 存儲 F(n)
復雜度分析
- 時間復雜度：兩種方法均為
O(n)，每個狀態僅計算一次。 - 空間復雜度：
- 方法一為
O(n)（存儲數組dp）。 - 方法二為
O(1)（僅用兩個變量迭代）。
- 方法一為
關鍵點
- 狀態轉移方程：明確子問題之間的關系，是動態規劃的核心。
- 邊界條件：正確初始化
dp[0]和dp[1]，避免邏輯錯誤。 - 空間優化：利用問題特性（僅依賴前兩項），減少內存占用，提升效率。
示例驗證
當 n = 6 時：
- 常規方法：
dp[2]=1,dp[3]=2,dp[4]=3,dp[5]=5,dp[6]=8，返回8。 - 優化方法：通過迭代計算，最終
prev2為8，結果一致。
通過動態規劃，斐波那契數列的求解效率從遞歸的指數級（O(2^n)）提升至線性級（O(n)），是重疊子問題和最優子結構的經典應用。
題目描述（課件中的路徑計數問題）
在一個 m×n 的網格 中，從左上角起點 (0, 0) 移動到右下角終點 (m-1, n-1)，每次只能 向下（Row+1）或向右（Col+1） 移動一步。網格中某些單元格為 障礙物（非空地），若單元格 (i,j) 是障礙物，則無法通過。求從起點到終點的 路徑總數。
網格路徑示意圖
最優解答（Python）
def count_paths(grid: list[list[bool]]) -> int:m, n = len(grid), len(grid[0])dp = [[0] * n for _ in range(m)]dp[m-1][n-1] = 1 if not grid[m-1][n-1] else 0for i in range(m-1, -1, -1):for j in range(n-1, -1, -1):if i == m-1 and j == n-1:continueif grid[i][j]:dp[i][j] = 0continuedown = dp[i+1][j] if i+1 < m else 0right = dp[i][j+1] if j+1 < n else 0dp[i][j] = down + rightreturn dp[0][0]# 示例測試
if __name__ == "__main__":grid = [[False, False, False],[False, False, False],[False, False, False]]print(count_paths(grid)) # 輸出: 6
答案解析
1. 動態規劃核心思路（課件要點）
- 狀態定義：
dp[i][j]表示從(i,j)到終點的路徑數，障礙物單元格路徑數為0。 - 狀態轉移：
dp[i][j] = dp[i+1][j] + dp[i][j+1]（下方和右方路徑數之和），與課件中“累加關系”的狀態轉移方程一致。 - 倒推計算：從終點向上、向左遞推，避免起點邊界特殊處理，符合課件中“從最下面依次往上”的思路。
2. 復雜度與關鍵點
- 時間/空間復雜度均為
O(m×n)，通過二維數組存儲中間狀態，確保每個單元格僅計算一次。 - 障礙物判斷直接決定當前單元格路徑數是否為
0，是課件中“if a[i,j]=‘空地’”條件的代碼實現。
該解答結合課件核心思想與圖片可視化，清晰呈現動態規劃在路徑計數問題中的應用。
)
安裝與使用---實踐)
