LeetCode 576. 出界的路径数

2023-04-03 HGNULB 约 11 分钟

文章信息 6 个分类 1 个标签

分类

题目描述

✅ 576. 出界的路径数

题意分析

在一个 m × n 的网格里，球从 (startRow, startColumn) 出发。每一步可以向上下左右四个方向之一移动一格，最多移动 maxMove 步。一旦球移出网格边界，这条路径就算成功并停止。问一共有多少条不同的路径能把球移出边界，结果对 $10^9 + 7$ 取模。

有几处必须读准。第一，统计的是路径数而不是方案是否存在，所以每一条走法都要单独计数，同一个格子被不同路径经过要分别累加。第二，出界即终止，出界之后不再继续移动，因此一条 3 步出界的路径和一条 5 步出界的路径是两条不同的路径，不存在「先出界再走回来」的情况。第三，maxMove 是上界而非定值，用掉 1 步出界和用掉 maxMove 步出界都算数。

「结果要取模」这个要求本身就是信号：说明答案可能是天文数字，不可能靠枚举路径来数。事实上四个方向、最多 maxMove 步，朴素枚举是 $4^{maxMove}$ 条路径，maxMove 取到 50 就已经完全不可行。

真正的算法信号在于：球接下来能怎么走，只取决于「它现在在哪个格子」和「还剩几步」，跟它是怎么走到这里的毫无关系。既然历史可以忘掉，状态空间就只有「步数 × 格子」这么大，即 $maxMove \cdot m \cdot n$，在题目给定的规模（网格 50×50、步数 50）下只有十几万，完全可以逐个算。

边界：maxMove 可能为 0，此时一步都不能走，答案是 0；起点本身一定在网格内；网格可能只有一行或一列，此时同一个格子的多个方向都会出界，必须每个方向各计一次，不能合并。取模要在每次累加后立即执行，否则中间和会突破 32 位整数。

解法：按步数滚动 DP

核心思路

暴力是从起点做深搜，每层枚举四个方向，走满 maxMove 步或出界为止。分支因子 4、深度 maxMove，共 $4^{maxMove}$ 条路径——maxMove = 50 时是天文数字。

搜索树上的重复非常明显：无数条不同的前缀路径会在「第 k 步结束时停在格子 (r, c)」这个局面上汇合，而从这个局面出发能贡献多少条出界路径是完全一样的。既然如此，就不该按路径展开，而应该按局面聚合——把「有多少条路径走到了这个局面」记成一个数，让它们一起往下走。

于是定义状态：dp[step][r][c] = 恰好走了 step 步之后，球停在格子 (r, c) 的路径条数。初始状态是 dp[0][startRow][startColumn] = 1（一步没走，只有一种「路径」，就是待在起点），其余为 0。

转移采用推式（从当前格子往外推），而不是拉式（从四周往当前格子拉）：对每个 dp[step][r][c] > 0 的格子，枚举四个方向的落点 (nr, nc)。若落点在界外，说明这 dp[step][r][c] 条路径都在第 step + 1 步出界了，直接把它们加进答案；若落点仍在界内，就把这些路径累加到 dp[step+1][nr][nc]。

推式在这里比拉式更自然，原因就在于「出界」这个去向没有对应的格子可以存放——出界的路径不再有位置，只能立刻结算进答案。用推式时，出界与不出界只是同一个 if 的两个分支，写起来对称而清晰。

答案的正确性依赖一个关键点：每一步的出界都被独立累加，且累加后这些路径不再参与后续状态。这自动实现了「出界即终止」——出界的路径没有被写进 next，下一轮自然不会再让它们移动，因此不会重复计数。

由于 dp[step+1] 只依赖 dp[step]，第一维可以整个丢掉，用两个 m × n 的二维数组滚动。这里必须每轮新建一个全零的 next，绝不能就地修改 dp：就地修改会让刚在本轮更新过的格子被当作本轮的起点再次向外推，等价于一步走了两格。

循环不变量：第 step 轮迭代开始时，dp[r][c] 恰好等于「用了 step - 1 步走到 (r, c) 且中途从未出界」的路径条数；answer 恰好等于「在前 step - 1 步内已经出界」的路径条数。

解题步骤

建 m × n 的 dp 数组，令 dp[startRow][startColumn] = 1，答案 answer = 0。为什么：1 表示「走 0 步停在起点」这唯一一条空路径，它是所有后续路径的共同前缀；其余格子为 0 表示走 0 步不可能到达。数组默认全零恰好符合这个语义，不需要额外初始化。

准备四方向增量表 {{0,1},{0,-1},{1,0},{-1,0}}。为什么：把方向数据化后，转移就是一个统一的循环，不必写四段几乎相同的代码；也便于日后改成八方向或棋盘跳跃。

外层循环 step 从 1 到 maxMove，每轮新建一个全零的 next 数组。为什么：循环次数就是允许的最大步数，maxMove = 0 时循环一次都不进、直接返回 0，边界天然成立；新建数组是为了严格分离「本轮之前」和「本轮之后」的状态，就地修改会让同一步被走两次。

遍历所有格子，dp[r][c] == 0 时直接跳过。为什么：没有任何路径到达的格子推不出东西，跳过是纯粹的剪枝；不跳过也正确，只是白做四次加零。

对四个方向算出落点 (nr, nc)，若越界则 answer = (answer + dp[r][c]) % mod。为什么：dp[r][c] 条路径在这一步全部出界，每条都是一条独立的合法答案，所以整体累加；出界后它们不写入 next，自动实现了「出界即终止、不再移动」，杜绝重复计数。

落点在界内时 next[nr][nc] = (next[nr][nc] + dp[r][c]) % mod。为什么：从 (r, c) 走一步到 (nr, nc) 的路径条数等于到达 (r, c) 的条数；同一个 (nr, nc) 可能被多个方向、多个来源格子写入，所以是累加而不是赋值。每次加完立刻取模，防止溢出。

本轮结束后令 dp = next。为什么：滚动到下一步；换引用是 $O(1)$，不需要拷贝。

循环结束返回 answer。为什么：answer 在每一步都实时累加了当步出界的路径，循环跑满 maxMove 轮后它就是全部答案；dp 中残留的是「走满 maxMove 步仍在界内」的路径，它们不算数，直接丢弃。

以 m = 2, n = 2, maxMove = 2, startRow = 0, startColumn = 0 走一遍（正确答案是 6）。

初始：dp = [[1, 0], [0, 0]]，answer = 0。

第 1 步：只有 (0,0) 非零，值为 1。四个方向依次是：右 (0,1) 在界内，next[0][1] += 1；左 (0,-1) 越界，answer += 1 变成 1；下 (1,0) 在界内，next[1][0] += 1；上 (-1,0) 越界，answer += 1 变成 2。本轮结束 dp = [[0, 1], [1, 0]]，answer = 2。

第 2 步：(0,1) 值为 1。右 (0,2) 越界，answer 变 3；左 (0,0) 在界内，next[0][0] += 1；下 (1,1) 在界内，next[1][1] += 1；上 (-1,1) 越界，answer 变 4。接着 (1,0) 值为 1。右 (1,1) 在界内，next[1][1] += 1 变成 2；左 (1,-1) 越界，answer 变 5；下 (2,0) 越界，answer 变 6；上 (0,0) 在界内，next[0][0] += 1 变成 2。本轮结束 dp = [[2, 0], [0, 2]]，answer = 6。

循环跑满，返回 6。逐条数一遍验证：第 1 步就出界的有 2 条（向左、向上）；第 2 步出界的有 4 条（先右后右、先右后上、先下后左、先下后下），合计 6 条。而 dp 里残留的那 4 条（先右后左、先右后下、先下后右、先下后上）走满 2 步仍在界内，正确地没有计入答案。

这个例子还顺带说明了为什么必须每轮新建 next：如果第 2 步就地在 dp 上累加，(0,1) 向左推到 (0,0) 后，(0,0) 会在同一轮的后续遍历中（若遍历顺序允许）被当作起点再次向外推，等于第 2 步走了两格。

代码实现

class Solution {
    public int findPaths(int m, int n, int maxMove, int startRow, int startColumn) {
        int mod = 1_000_000_007;
        int[][] dp = new int[m][n];
        // 走 0 步停在起点，只有一条空路径。
        dp[startRow][startColumn] = 1;
        int answer = 0;
        int[][] dirs = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

        for (int step = 1; step <= maxMove; step++) {
            // 每轮新建全零数组，严格分离「本轮之前」与「本轮之后」的状态。
            int[][] next = new int[m][n];
            for (int r = 0; r < m; r++) {
                for (int c = 0; c < n; c++) {
                    if (dp[r][c] == 0) {
                        continue;
                    }
                    for (int[] d : dirs) {
                        int nr = r + d[0];
                        int nc = c + d[1];
                        if (nr < 0 || nr >= m || nc < 0 || nc >= n) {
                            // 出界后不写入 next，自动实现「出界即终止」。
                            answer = (answer + dp[r][c]) % mod;
                        } else {
                            next[nr][nc] = (next[nr][nc] + dp[r][c]) % mod;
                        }
                    }
                }
            }
            dp = next;
        }

        return answer;
    }
}

func findPaths(m int, n int, maxMove int, startRow int, startColumn int) int {
	const mod = 1_000_000_007
	dp := make([][]int, m)
	for i := range dp {
		dp[i] = make([]int, n)
	}
	// 走 0 步停在起点，只有一条空路径。
	dp[startRow][startColumn] = 1

	answer := 0
	dirs := [][2]int{{0, 1}, {0, -1}, {1, 0}, {-1, 0}}
	for step := 1; step <= maxMove; step++ {
		// 每轮新建全零数组，严格分离「本轮之前」与「本轮之后」的状态。
		next := make([][]int, m)
		for i := range next {
			next[i] = make([]int, n)
		}
		for r := 0; r < m; r++ {
			for c := 0; c < n; c++ {
				if dp[r][c] == 0 {
					continue
				}
				for _, d := range dirs {
					nr, nc := r+d[0], c+d[1]
					if nr < 0 || nr >= m || nc < 0 || nc >= n {
						// 出界后不写入 next，自动实现「出界即终止」。
						answer = (answer + dp[r][c]) % mod
					} else {
						next[nr][nc] = (next[nr][nc] + dp[r][c]) % mod
					}
				}
			}
		}
		dp = next
	}

	return answer
}

复杂度分析

时间复杂度：$O(maxMove \cdot m \cdot n)$。凭什么：外层跑 maxMove 轮，每轮遍历全部 $m \cdot n$ 个格子，每个格子固定枚举 4 个方向、做一次越界判断和一次取模加法，方向数是常数因子。相比暴力枚举的 $4^{maxMove}$，省下的正是「不同前缀路径在同一局面汇合」的那部分重复。

空间复杂度：$O(m \cdot n)$。凭什么：任意时刻只同时存在 dp 与 next 两个 $m \times n$ 的数组，步数那一维被滚动掉了；若保留完整的三维表则是 $O(maxMove \cdot m \cdot n)$。方向表是常数大小。

关键点总结

「统计方案数」且「结果要取模」是 DP 的强信号：能取模说明不需要构造具体方案，只需要计数，而计数天然可以在局面上聚合。看到这两个词就该放弃搜索、转向递推。

判断能否用 DP，核心是问「未来是否只依赖当前局面」。本题里「在哪个格子 + 还剩几步」就是完整的局面描述，历史路径可以整个忘掉，$4^{maxMove}$ 随之塌缩成 $maxMove \cdot m \cdot n$。

推式与拉式的选择要看去向能否落地。本题的「出界」没有对应的格子来承接，只能立刻结算进答案，所以推式（从当前格往外推）比拉式（从四周往当前格拉）自然得多。这个判断标准在带「吸收态」的计数题里通用。

分层递推必须写进新数组再整体切换。就地覆盖会让本层刚更新的值被当作本层的输入再次使用，等价于一步走了两格——这是滚动数组最高频的 bug。

取模要在每次累加之后立刻做，而不是最后统一做。中间和一旦突破 32 位就已经丢失信息，最后再取模也救不回来。

易错点总结

就地在 dp 上累加而不新建 next：m = 2, n = 2, maxMove = 2 → 本轮刚被写入的格子在同轮遍历中再次向外推，一步走了两格，答案远大于 6。

出界后仍把路径写进 next：出界的路径下一轮继续移动 → 同一条路径被反复计入答案，结果随 maxMove 增大而爆炸式偏大。

四个方向出界时只累加一次：m = 1, n = 1, maxMove = 1 → 四个方向全部出界，正确答案是 4，合并计数会得到 1。

忘记取模或只在最后取模：m = 50, n = 50, maxMove = 50 → 中间和早已突破 int 上限、回绕成负数，最后取模也无法还原，返回负数或错误值。

dp[startRow][startColumn] 初始化成 0 或忘记初始化：任何输入 → 所有格子都是 0，没有任何路径可推，返回 0。

maxMove = 0 时未经检验就访问 dp 之外的东西：正确行为是循环不执行、直接返回 0；若把答案初始化成 1 或在循环外先结算一次，会错误地返回非零值。

越界判断写成 nr <= 0 || nr >= m：第 0 行的格子被误判为出界 → m = 2, n = 2 时第 0 行永远推不进 next，路径大量丢失。

越界判断只查行不查列：m = 1, n = 3 → 左右出界的路径被当作界内写入 next[0][-1]，直接数组越界抛异常。

把答案累加成 answer += 1 而不是 answer += dp[r][c]：m = 2, n = 2, maxMove = 3 时，多条路径会先汇合到同一格再出界；只加 1 会把这些不同路径压成一条而低估答案。

返回 dp 中所有值之和：那是「走满 maxMove 步仍在界内」的路径数 → 与题目要的出界路径数正好互补，答案完全对不上。

相似题目

题目	难度	考察点
688. 骑士在棋盘上的概率	中等	同为按步数分层扩散，但走的是日字八方向且每步带 $1/8$ 概率权重，求期望
62. 不同路径	中等	只能右和下，路径长度固定，无需按步数分层，直接按格子递推即可
63. 不同路径 II	中等	在 62 基础上加障碍物，障碍格状态置零，考的是「不可达」的表达方式
568. 最大休假天数	困难	同为「层 × 节点」分层递推，但求最大值而非计数，转移沿邻接矩阵进行
1289. 下降路径最小和 II	困难	逐行推进且转移是「除自己外所有列」，可用最小值与次小值把每层降到线性
494. 目标和	中等	同为方案计数，状态是「已处理几个数 + 当前和」，转移只有加减两个分支
518. 零钱兑换 II	中等	计数时要避免重复组合，靠「外层枚举物品」的遍历顺序保证组合不计顺序
377. 组合总和 Ⅳ	中等	与 518 的循环顺序正相反，统计排列数，正好对照理解遍历顺序的语义