Day 5：記憶化搜索（滑雪問題、斐波那契數列）
📖 一、記憶化搜索簡介
記憶化搜索（Memoization） 是一種優化遞歸的方法，它利用 哈希表（HashMap）或數組 存儲已經計算過的結果，避免重復計算，提高效率。
📌 記憶化搜索 vs 動態規劃
| 方法 | 特點 | 適用場景 |
|---|---|---|
| 記憶化搜索 | 自頂向下（遞歸 + 記憶化存儲） | 遞歸問題 |
| 動態規劃 | 自底向上（迭代 + 狀態轉移） | 適用于所有 DP 問題 |
📖 二、經典記憶化搜索問題
1. 滑雪問題
題目描述：
- 給定一個
n × m的矩陣，每個位置(i, j)代表海拔高度h(i, j)。 - 從某一點
(i, j)出發，可以向 上下左右 移動，前提是新的位置海拔嚴格低于當前點。 - 目標是求最長的滑雪路徑長度。
🔹 1. 思路
- 遞歸搜索所有可能的路徑。
- 由于路徑可能會重復訪問同一個點，我們用
dp[i][j]記憶化存儲(i, j)位置的最長滑雪路徑。
🔹 2. 代碼實現（滑雪問題）
import java.util.*;public class Skiing {static int[][] directions = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};static int[][] grid, dp;static int rows, cols;public static int longestSkiPath(int[][] matrix) {if (matrix == null || matrix.length == 0) return 0;rows = matrix.length;cols = matrix[0].length;grid = matrix;dp = new int[rows][cols];int maxPath = 0;for (int i = 0; i < rows; i++) {for (int j = 0; j < cols; j++) {maxPath = Math.max(maxPath, dfs(i, j));}}return maxPath;}private static int dfs(int i, int j) {if (dp[i][j] != 0) return dp[i][j]; // 記憶化：避免重復計算int maxLength = 1; // 初始長度for (int[] dir : directions) {int x = i + dir[0], y = j + dir[1];if (x >= 0 && x < rows && y >= 0 && y < cols && grid[x][y] < grid[i][j]) {maxLength = Math.max(maxLength, 1 + dfs(x, y));}}dp[i][j] = maxLength;return maxLength;}public static void main(String[] args) {int[][] matrix = {{9, 8, 7},{6, 5, 4},{3, 2, 1}};System.out.println("最長滑雪路徑長度: " + longestSkiPath(matrix)); // 輸出 9}
}
🔹 3. 代碼講解
dfs(i, j)遞歸查找(i, j)位置的最長路徑。dp[i][j]記憶化存儲 計算過的路徑，避免重復計算。- 四個方向搜索，如果高度下降，則遞歸搜索。
? 時間復雜度：O(n × m)（避免重復計算）。
📖 三、斐波那契數列（Fibonacci）
題目描述： 斐波那契數列定義如下：
F(n)=F(n?1)+F(n?2),F(0)=0,F(1)=1F(n) = F(n-1) + F(n-2), \quad F(0) = 0, \quad F(1) = 1
求 F(n)。
🔹 1. 代碼實現（記憶化搜索版）
import java.util.*;public class FibonacciMemoization {static Map<Integer, Long> memo = new HashMap<>();public static long fibonacci(int n) {if (n == 0) return 0;if (n == 1) return 1;if (memo.containsKey(n)) return memo.get(n);long result = fibonacci(n - 1) + fibonacci(n - 2);memo.put(n, result);return result;}public static void main(String[] args) {System.out.println("Fibonacci(50): " + fibonacci(50)); // 輸出很快}
}
? 時間復雜度：O(n)，避免 O(2^n) 的指數級遞歸。
📖 四、藍橋杯真題：2021省賽 - 冰雹數
題目描述： 冰雹數列定義如下：
Hail(n) = n / 2（如果n是偶數）。Hail(n) = 3n + 1（如果n是奇數）。- 繼續計算直到
n = 1，求Hail(n)的長度。
示例
輸入: 10
輸出: 7
🔹 1. 代碼實現（記憶化搜索）
import java.util.*;public class HailstoneSequence {static Map<Integer, Integer> memo = new HashMap<>();public static int hailstoneLength(int n) {if (n == 1) return 1;if (memo.containsKey(n)) return memo.get(n);int next = (n % 2 == 0) ? n / 2 : 3 * n + 1;int length = 1 + hailstoneLength(next);memo.put(n, length);return length;}public static void main(String[] args) {int n = 10;System.out.println("冰雹數列長度: " + hailstoneLength(n)); // 輸出 7}
}
🔹 2. 代碼講解
hailstoneLength(n)遞歸計算n的冰雹序列長度。memo記憶化存儲 已計算的n，避免重復計算。
? 時間復雜度：O(n)，避免 O(2^n) 級別的計算。
📖 五、總結
1. 記憶化搜索 vs 動態規劃
| 方法 | 優點 | 缺點 |
|---|---|---|
| 記憶化搜索（自頂向下） | 直觀，遞歸寫法清晰 | 可能有遞歸棧溢出 |
| 動態規劃（自底向上） | 迭代方式，減少遞歸棧使用 | 需要找到最優狀態轉移方程 |
2. 記憶化搜索應用場景
? 斐波那契數列：避免指數級遞歸。
? 最長路徑問題（滑雪）：存儲已訪問路徑，避免重復計算。
? 數論問題（冰雹數）：存儲已計算結果，避免深度遞歸。
工具)
