算法刷题系列（四十七）：记忆化搜索——缓存重复递归状态

算法刷题系列（四十七）：记忆化搜索——缓存重复递归状态

递归很自然地表达“从当前位置继续做选择”，但不同选择路径可能到达同一个子问题。若每次都重新计算，递归树会重复展开；记忆化搜索把子问题答案缓存起来，让每个状态只计算一次。

本文计算网格中从左上角走到右下角的路径数。每一步只能向右或向下，true 表示障碍格，不能经过。状态 solve(r,c) 表示从格子 (r,c) 到终点的路径数。

状态、转移和缓存

• 越界或落在障碍格：返回 0；
• 到达终点：返回 1；
• 其他格：solve(r+1,c) + solve(r,c+1)。

递归会从不同路径汇合到同一个格子。缓存键是 (r,c)，已计算的结果直接返回。不变量：缓存中的每个状态都等于从该格子出发的真实路径数；递归严格向右或向下，行列坐标至少一个增加，因此不存在环，最终会到达边界或终点。

这个网格例子中状态数量最多为 rows × columns，每个状态只做常数次转移。记忆化并未改变递推关系，只消除了重复计算；它可以看作自顶向下的动态规划。

Java 实现

import java.util.Arrays;

public class Main {
    static long countPaths(boolean[][] blocked) {
        if (blocked == null) throw new IllegalArgumentException("grid must not be null");
        int rows = blocked.length;
        if (rows == 0) return 0;
        if (blocked[0] == null) throw new IllegalArgumentException("rows must not be null");
        int cols = blocked[0].length;
        for (boolean[] row : blocked) {
            if (row == null || row.length != cols) throw new IllegalArgumentException("grid must be rectangular");
        }
        if (cols == 0 || blocked[0][0] || blocked[rows - 1][cols - 1]) return 0;
        long[][] memo = new long[rows][cols];
        for (long[] row : memo) Arrays.fill(row, -1);
        return solve(0, 0, blocked, memo);
    }

    private static long solve(int r, int c, boolean[][] blocked, long[][] memo) {
        int rows = blocked.length, cols = blocked[0].length;
        if (r >= rows || c >= cols || blocked[r][c]) return 0;
        if (r == rows - 1 && c == cols - 1) return 1;
        if (memo[r][c] != -1) return memo[r][c];
        memo[r][c] = solve(r + 1, c, blocked, memo)
                   + solve(r, c + 1, blocked, memo);
        return memo[r][c];
    }

    public static void main(String[] args) {
        boolean[][] grid = {
            {false, false, false},
            {false, true,  false},
            {false, false, false}
        };
        System.out.println(countPaths(grid)); // 2
    }
}

Python 实现

from functools import lru_cache

def count_paths(blocked: list[list[bool]]) -> int:
    if blocked is None:
        raise ValueError("grid must not be None")
    if not blocked:
        return 0
    if any(row is None for row in blocked):
        raise ValueError("rows must not be None")
    cols = len(blocked[0])
    if any(len(row) != cols for row in blocked):
        raise ValueError("grid must be rectangular")
    rows = len(blocked)
    if cols == 0 or blocked[0][0] or blocked[-1][-1]:
        return 0

    @lru_cache(maxsize=None)
    def solve(r: int, c: int) -> int:
        if r >= rows or c >= cols or blocked[r][c]:
            return 0
        if r == rows - 1 and c == cols - 1:
            return 1
        return solve(r + 1, c) + solve(r, c + 1)

    return solve(0, 0)

assert count_paths([[False, False, False], [False, True, False], [False, False, False]]) == 2
assert count_paths([[False]]) == 1
assert count_paths([[True]]) == 0
assert count_paths([]) == 0
assert count_paths([[], []]) == 0

复杂度与常见错误

令网格大小为 R × C，时间和缓存空间都是 O(RC)；递归栈深度最坏为 O(R+C)。Java long 有上限，若路径数可能超出范围，需要使用大整数或按题意取模。非常深的递归也可能超过语言调用栈，此时可改成自底向上的表格 DP。

关键错误包括漏掉缓存导致指数级重复、缓存键缺少影响答案的状态变量、把“未计算”与合法答案 0 混为一谈，以及错误处理边界导致越界访问。若题目还受到剩余体力、已使用资源或阶段影响，状态就不能只用坐标，必须把这些信息加入缓存键。递归转移还应保证状态图无环，或者另行处理循环依赖。

小结

记忆化搜索先定义完整状态，再用递归写出状态转移，并缓存每个状态的答案。它特别适合“从一个状态尝试若干后继”的题目；明确状态范围和依赖方向，才能确保缓存既正确又有效。