题目描述
机器人在 m×n 网格左上角，每次只能向右或向下，到右下角共几条路径？
网格 = 3 × 3
输出 = 6
思路解析
一条条枚举走法，3×3 就有 6 条；网格一大，走法数就是组合数 C(m+n−2, n−1)，爆炸式增长，根本数不过来。问题在于同一个格子被反复重复经过、重复计算。
与其重复数每条路，不如把每个格子的走法数记进一张表。一个格子只能从上面或左边过来，所以 dp[i][j] = 上 + 左 = dp[i-1][j] + dp[i][j-1]——上、左早算好了，直接查表相加，绝不重算。
建表：建一张 3×3 的表，每格存「到这里的路径数」。
先想清楚状态：dp[i][j] 表示从左上角走到第 i 行第 j 列共有几条路。终点就是右下角 dp[2][2]。
第一行、第一列 = 1：最上行只能一路向右、最左列只能一路向下，各只有 1 种走法，先填 1。
关键：上 + 左：中间格子 = 正上方 + 左边。dp[1][1] = 1 + 1 = 2。
填 dp[1][2]：同样规则：上面 1 + 左边 2 = 3。
填 dp[2][1]：再填 dp[2][1]：上面 2 + 左边 1 = 3。每个格子都这么算。
填到右下角：一路填满，右下角 dp[2][2] = 3 + 3 = 6，就是答案。
DP 说白了就是「走过的路记下来，绝不重复算」。「每格只看上和左」只是这个思想落在网格里的样子——最小路径和、三角形最小和都是同一招。
参考代码（Python）
Python
1dp = [[0]*n for _ in range(m)]
2for i in range(m): dp[i][0] = 1 # 第一列
3for j in range(n): dp[0][j] = 1 # 第一行
4for i in range(1, m):
5 for j in range(1, n):
6 dp[i][j] = dp[i-1][j] + dp[i][j-1]
7return dp[m-1][n-1]复杂度分析
- 时间复杂度：O(m×n) —— 每格算一次
- 空间复杂度：O(m×n) —— 二维表；可压成一行
套路模板
骨架：先定第一行/列边界，再双层循环把「上和左」合并。求路径数就用「相加」；最小路径和把「合并」换成 min、再加当前格代价，一题变多题。
Python
1# 凡是「网格里从左上走到右下」的题都能套
2dp = [[0]*n for _ in range(m)]
3for i in range(m): dp[i][0] = 边界值 # 第一列
4for j in range(n): dp[0][j] = 边界值 # 第一行
5for i in range(1, m):
6 for j in range(1, n):
7 dp[i][j] = 合并(dp[i-1][j], dp[i][j-1]) + 当前格
8return dp[m-1][n-1]易错点
- ❌ 忘了初始化第一行/列 → ✅ 先把第一行、第一列填好（它们没有「上」或「左」，要单独定边界）
- ❌ 内层从 0 开始 → ✅ 从 1 开始（边界已填）（否则会用到不存在的 dp[-1]）
以上文字与上方动画完全同一思路：先看动画建立直觉 → 读文字巩固 → 关掉页面自己默写一遍代码，能写出来才算真的掌握。