数据结构与算法 / 系统课时

递归问题的状态设计

递归问题的状态设计

递归题真正难的是定义“当前调用正在解决什么子问题”。本课用带障碍网格路径计数,完成状态、选择、终止条件与记忆化缓存的统一设计,并说明如何由状态规模判断复杂度。

学习目标

  • 用函数参数完整描述一个递归子问题
  • 根据合法选择写出递推关系与终止条件
  • 使用记忆化缓存消除重复计算

从函数含义定义状态

先用一句话固定函数含义:

text
f(row, column) = 从位置 (row, column) 到右下角的合法路径数量

row 和 column 必须足以唯一确定子问题。若两个调用参数相同,它们的后续选择和返回值也应相同,否则状态中还缺少变量。例如结果还依赖剩余步数时,缓存键也必须包含 stepsLeft。

合格的状态应满足三点:含义明确、信息充分、变量尽量精简。不要把“已经走过的完整路径”放进状态,除非后续决策确实依赖它。

从选择得到递推与终止条件

当前位置只能向下或向右,因此递推关系为:

f(r,c)=f(r+1,c)+f(r,c+1)f(r,c)=f(r+1,c)+f(r,c+1)

越界或遇到障碍时返回 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)。

缓存键必须覆盖所有会影响返回值的状态变量。若递归深度可能很大,还应评估栈溢出风险,并考虑改写为自底向上的动态规划。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

递归问题的状态设计

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通