蓝桥杯 Java B 组之记忆化搜索（滑雪问题、斐波那契数列）

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 动态规划

方法	优点	缺点
记忆化搜索（自顶向下）	直观，递归写法清晰	可能有递归栈溢出
动态规划（自底向上）	迭代方式，减少递归栈使用	需要找到最优状态转移方程