题目描述
机器人在 m×n 网格左上角，每次只能向右或向下，到右下角共几条路径？
思路解析
一条条枚举走法，3×3 还能硬数出 6 条；网格一大，走法数就是组合数 C(m+n−2, n−1)，爆炸式增长，根本数不过来。痛点在于：同一个格子被反复经过、重复计算——左上角那块路径，几乎每条大路都要重新走一遍。
与其重复数每条路，不如把每个格子的走法数记进一张表。一个格子只能从上面或左边过来，所以 dp[i][j] = 上 + 左 = dp[i-1][j] + dp[i][j-1]。为什么能这么拆？因为「到 (i,j) 的路」按最后一步是「从上来」还是「从左来」不重不漏地分成两类，而上、左两格早算好了——直接查表相加，绝不重算。
建表：建一张 3×3 的表，每格存「到这里的路径数」。起点 (0,0) 只有 1 种走法（站着不动），先把它当锚点。终点是右下角 dp[2][2]，咱一格一格填过去。
第一行 = 1：最上面一行没有「上面」可来，只能从起点一路向右，所以到行0每一格都只有 1 种走法，全填 1。
第一列 = 1：同理，最左边一列没有「左边」可来，只能一路向下，每格也是 1。第一行、第一列是边界——它们撑不起转移方程，必须单独定。
关键：上 + 左：第一个真正用到转移方程的格子。dp[1][1] 看两个依赖格：正上方 dp[0][1]=1、正左方 dp[1][0]=1，相加 = 2。这就是「上 + 左」。
填 dp[1][2]：同一招：上面 dp[0][2]=1，左边 dp[1][1]=2（刚算出来的），相加 = 3。注意左边那格的答案是上一步现成存好的，直接拿来用。
填 dp[2][1]：换到第三行。dp[2][1] 的上面是 dp[1][1]=2、左边是 dp[2][0]=1，相加 = 3。填表顺序从上到下、从左到右，保证依赖格永远先算好。
填到右下角：终点格。上面 dp[1][2]=3，左边 dp[2][1]=3，相加 = 6。两条「来路」各 3 条，合起来正好 6。
答案：表填满了，右下角 dp[2][2] = 6 就是答案，和一开始手数的 6 条路完全对上。
DP 说白了就是「走过的路记下来，绝不重复算」。「每格只看上和左」只是这个思想落在网格里的样子——最小路径和、三角形最小和都是同一招。
参考代码（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) —— 每格只算一次，共 m×n 格
- 空间复杂度：O(m×n) —— 二维表；可压成一行 O(n)
套路模板
骨架：先定第一行/列边界，再双层循环把「上和左」合并。求路径数就用「相加」；最小路径和把「合并」换成 min、再加当前格代价，一题变多题。
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]易错点
- 错误写法：第一行/列不初始化为 1 → 正确写法：先把第一行、第一列每格填 1（边界格没有「上」或「左」可加；不填成 1，dp[1][1] 就会从一堆 0 算出 0，整张表全错）
- 错误写法：内层 j 从 0 开始 → 正确写法：i、j 都从 1 开始（边界已填）（从 0 开始会访问 dp[i][-1]，在 Python 里悄悄取到末列，数值错得没报错）
以上文字与上方动画完全同一思路：先看动画建立直觉 → 读文字巩固 → 关掉页面自己默写一遍代码，能写出来才算真的掌握。