HJ91. 走方格的方案数
题目描述
在 n×m 的方格矩阵中，从左上角走到右下角，每次只能向右或向下走一格，问有多少种不同的走法。
输入格式
一行两个整数 n、m。
输出格式
方案数（整数）。
示例
示例 1
输入：
2 3
输出：
10
说明： 2 行 3 列的方格，从左上角到右下角共有 10 种走法。
解题思路
第一步：理解问题本质
从左上角 (0,0) 走到右下角 (n,m)，每次向右或向下。总步数固定为 n+m 步，其中向下 n 步、向右 m 步。问题等价于在 n+m 个位置中选出 n 个向下。
第二步：暴力解法（DFS 枚举路径）
从 (0,0) 出发递归，向右或向下，到达 (n,m) 时计数。每条路径都要完整遍历，路径数呈组合数增长，当 n、m 较大时指数级，无法接受。
第三步：优化解法（二维 DP）
定义 dp[i][j] 为从 (0,0) 到 (i,j) 的方案数：
- 边界：第一行、第一列都只能直线走，均为 1
- 转移：
dp[i][j] = dp[i-1][j] + dp[i][j-1]（来自上方 + 来自左方）
dp = [[0] * (m + 1) for _ in range(n + 1)]
for i in range(n + 1):
dp[i][0] = 1
for j in range(m + 1):
dp[0][j] = 1
for i in range(1, n + 1):
for j in range(1, m + 1):
dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
print(dp[n][m])
复杂度 O(n·m)。
第四步：最优解法（组合数公式）
到达终点需要 n 次向下、m 次向右，共 n+m 步。方案数即从 n+m 步中选出 n 步向下的组合数：C(n+m, n)。直接代入公式即可，O(n) 计算。
完整代码实现
算法可视化 · 逐帧回放这道题的代码35 帧 · 录制输入
import sys
def solve() -> None:
n, m = map(int, sys.stdin.readline().split())
# dp[i][j] 表示从 (0,0) 到 (i,j) 的方案数
dp = [[0] * (m + 1) for _ in range(n + 1)]
for i in range(n + 1):
dp[i][0] = 1 # 第一列只有向下一路
for j in range(m + 1):
dp[0][j] = 1 # 第一行只有向右一路
for i in range(1, n + 1):
for j in range(1, m + 1):
dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
print(dp[n][m])
if __name__ == "__main__":
solve()
示例推演
以示例 1 为例，n=2，m=3，方格为 2 行 3 列。
初始化边界：
1 1 1 1
1 . . .
1 . . .
逐格递推：
dp[1][1] = dp[0][1] + dp[1][0] = 1 + 1 = 2dp[1][2] = dp[0][2] + dp[1][1] = 1 + 2 = 3dp[1][3] = dp[0][3] + dp[1][2] = 1 + 3 = 4dp[2][1] = dp[1][1] + dp[2][0] = 2 + 1 = 3dp[2][2] = dp[1][2] + dp[2][1] = 3 + 3 = 6dp[2][3] = dp[1][3] + dp[2][2] = 4 + 6 = 10
答案 dp[2][3] = 10。
复杂度分析
| 解法 | 时间复杂度 | 空间复杂度 | 说明 |
|---|---|---|---|
| DFS 枚举 | O(C(n+m,n)) | O(n+m) | 指数级，不可行 |
| 二维 DP | O(n·m) | O(n·m) | 标准递推表 |
| 组合数公式 | O(min(n,m)) | O(1) | 直接计算 C(n+m, n) |
易错点总结
1. 边界初始化为 0
第一行、第一列必须初始化为 1，否则所有格子递推结果恒为 0。
2. n、m 含义搞混
n 表示行（向下）、m 表示列（向右），DP 数组维度是 (n+1) × (m+1)，不能写反。
3. 忘了 0 的情况
当 n=0 或 m=0 时只有一条直线路径，方案数为 1，DP 边界初始化已覆盖此情况。
扩展思考
- 若加入障碍物（某些格子不可走），只需把对应
dp置 0，转移不变。 - 组合数公式可配合取模处理超大 n、m（大组合数取模需用逆元或卢卡斯定理）。