数据结构与算法 / 系统课时
递归问题的状态设计
递归问题的状态设计
递归题真正难的是定义“当前调用正在解决什么子问题”。本课用带障碍网格路径计数,完成状态、选择、终止条件与记忆化缓存的统一设计,并说明如何由状态规模判断复杂度。
学习目标
- 用函数参数完整描述一个递归子问题
- 根据合法选择写出递推关系与终止条件
- 使用记忆化缓存消除重复计算
从函数含义定义状态
先用一句话固定函数含义:
text
f(row, column) = 从位置 (row, column) 到右下角的合法路径数量row 和 column 必须足以唯一确定子问题。若两个调用参数相同,它们的后续选择和返回值也应相同,否则状态中还缺少变量。例如结果还依赖剩余步数时,缓存键也必须包含 stepsLeft。
合格的状态应满足三点:含义明确、信息充分、变量尽量精简。不要把“已经走过的完整路径”放进状态,除非后续决策确实依赖它。
从选择得到递推与终止条件
当前位置只能向下或向右,因此递推关系为:
越界或遇到障碍时返回 0,表示该分支不能贡献路径;到达终点时返回 1,表示得到一条完整路径。判断顺序应先排除越界和障碍,再判断终点,避免访问非法下标或把障碍终点计为有效路径。

主示例:带障碍网格路径计数
下面的 Java 17 程序使用 memo[row][column] 缓存每个位置的路径数量。缓存先填充为 -1,从而区分“尚未计算”和合法结果 0。
java
import java.util.Arrays;
public class RecursiveStateDesignDemo {
private static final int BLOCKED = 1;
private static final int UNCOMPUTED = -1;
public static void main(String[] args) {
int[][] grid = {
{0, 0, 0},
{0, 1, 0},
{0, 0, 0}
};
int[][] memo = new int[grid.length][grid[0].length];
for (int[] row : memo) {
Arrays.fill(row, UNCOMPUTED);
}
int count = countPaths(grid, 0, 0, memo);
System.out.println("路径数量: " + count);
}
private static int countPaths(
int[][] grid,
int row,
int column,
int[][] memo
) {
// 先排除非法状态,避免数组越界。
if (row >= grid.length || column >= grid[0].length) {
return 0;
}
if (grid[row][column] == BLOCKED) {
return 0;
}
if (row == grid.length - 1 && column == grid[0].length - 1) {
return 1;
}
if (memo[row][column] != UNCOMPUTED) {
return memo[row][column];
}
int down = countPaths(grid, row + 1, column, memo);
int right = countPaths(grid, row, column + 1, memo);
memo[row][column] = down + right;
return memo[row][column];
}
}预期输出:
text
路径数量: 2中心位置是障碍,合法路径只有“沿上边界后向下”和“沿左边界后向右”两条。
复杂度与边界
若网格有 m 行、n 列,状态总数最多为 m × n。记忆化后每个状态只计算一次,时间复杂度为 O(m × n);缓存占用 O(m × n),递归栈最深为 O(m + n)。
缓存键必须覆盖所有会影响返回值的状态变量。若递归深度可能很大,还应评估栈溢出风险,并考虑改写为自底向上的动态规划。
按自己的节奏,确认真正理解。