企业官网建设流程全解析

1. 题目到底在问什么：先理解“n*m方格前进问题”

动态规划是算法面试里绕不开的一块内容，而“n*m方格前进问题”差不多是动态规划里最经典的入门题型之一。很多人在网上看了一堆动态规划的教程，什么状态转移、最优子结构、重叠子问题，名词背了一大堆，拿到这道题还是不知道从哪下手。原因很简单：抽象概念听再多，不如亲手把一道题从暴力递归改到动态规划，来一遍完整的心智过程。

这道题最常见的描述是这样：一个机器人位于一个 n 行 m 列的网格左上角，每次只能向右或者向下移动一步，问到达右下角一共有多少条不同的路径。有些版本会加障碍物，有些版本会问最短路径和，但最基础、最干净的就是这个“只走右和下”的计数问题。

先说结论：这个问题的答案不是靠模拟一步一步走出来的，而是靠“拆”。你站在任何一个格子上，能走到这个格子的方式只有两种——从上面走下来，或者从左边走过来。所以到达当前格子的路径总数，就等于到达上方格子的路径总数加上到达左方格子的路径总数。如果你把每一个格子的这个数值都填出来，最后右下角那个数字就是答案。

听起来很简单对不对？但这里面的“为什么能这么拆”“为什么拆完不会重复不会漏”“为什么可以用数组来存”才是动态规划的精髓。这篇文章我不打算只甩一个公式给你，而是把从审题、建模、写代码、优化到踩坑的完整过程全部过一遍，保证你看完之后不仅能写对这道题，还能把它背上的那层皮扒干净，以后遇到类似的题心里都有底。

适合谁来读？正在学算法的学生、准备面试的开发者、刷 LeetCode 卡在动态规划入门的同学，都适合。这道题本身不难，但它背后牵出的“状态定义 + 转移方程 + 初始化 + 遍历顺序”四件套，是你之后面对所有动态规划题目的通用框架。

2. 为什么暴力搜索行不通：先算一笔复杂度的账

很多第一次看到这道题的人，第一反应是：那我就用深搜 DFS 呗，从起点开始，每次往右或往下走，走到终点就计数加一。这个思路没有错，甚至在逻辑上非常直观，但问题是：它跑不完。

2.1 暴力搜索到底会遍历多少条路径

我们算一下。一个 n 行 m 列的网格，从左上角走到右下角，因为只能向右和向下走，所以总共需要走 (n - 1) + (m - 1) = n + m - 2 步，其中向下走 n - 1 步，向右走 m - 1 步。路径总数是组合数 C(n + m - 2, n - 1)，也就是从总步数里选出哪几步向下走。

这个数涨得有多快？我随手列几个值你感受一下：

• 3 行 3 列：C(4, 2) = 6 条
• 5 行 5 列：C(8, 4) = 70 条
• 8 行 8 列：C(14, 7) = 3432 条
• 10 行 10 列：C(18, 9) = 48620 条
• 15 行 15 列：C(28, 14) = 40116600 条
• 18 行 18 列：C(34, 17)，大概 23 亿条

也就是说，20 行 20 列以内的网格，暴力搜索就已经是亿级别的访问量了。就算每一条路径只做常数次操作，跑起来也是秒级起步，再大一点直接指数爆炸。面试官让你手写这道题，如果丢一个 DFS 上去，基本就是送人头的。

2.2 重复计算是罪魁祸首

暴力搜索慢，不是因为“走的路径多”这个现象本身，而是因为大量子问题被反复计算。什么叫重复计算？你从起点出发，有无数种方式走到中间某个格子 (i, j)，但一旦走到了 (i, j)，之后到终点的路径数其实是固定的。DFS 的做法是每一条完整路径都从头走一遍，相当于同一个“从 (i, j) 到终点的路径数”被反复算了几百次、几千次。

动态规划干的事情，就是把这个共享的“中间结果”存下来，用一次就算一次，之后直接查表。这就是所谓的“用空间换时间”。明白了这一点，你就知道为什么动态规划能把这个指数级的问题降到多项式级——因为整个网格一共只有 n 乘 m 个格子，每个格子只需要算一次。

我之前带过不少同学，很多人卡住不是因为不知道状态转移怎么写，而是没想明白“为什么不能直接 DFS”。我建议你从第一步开始就建立这个认知：动态规划不是一种花哨的技巧，它就是一种“聪明地复用中间结果”的暴力搜索。想通了这一点，后面所有代码都是在给这句话做注脚。

3. 核心建模：状态定义、转移方程、初始化与遍历顺序

动态规划的解题目套路，说来说去就是四件事：状态定义、转移方程、初始化、遍历顺序。这一节我把每一件都拆开讲透，而且每一件都会回答“为什么”，而不是只告诉你“是什么”。

3.1 状态定义：dp[i][j] 到底代表什么

对于这道题，最自然的状态定义是：dp[i][j] 表示从左上角 (0, 0) 出发，到达格子 (i, j) 的路径总数。

这里的 i 表示行号，j 表示列号，范围分别是 0 到 n-1 和 0 到 m-1。下标从 0 开始还是从 1 开始，纯粹是个人习惯问题。我个人更推荐从 0 开始，因为和数组下标天然对齐，写代码的时候少做一次转换。如果你从 1 开始，状态定义就变成“到达第 i 行第 j 列的路径总数”，边界条件会稍微好写一点，但本质上没有任何区别。

状态定义是整个动态规划题里最重要的一步，比转移方程还重要。因为一旦状态定义得不好，后面的转移方程怎么都推不顺。反过来，状态定义好了，转移方程通常是顺手写出来的。这个道理在你以后做更复杂的动态规划题时会反复应验。

3.2 转移方程：从哪来，比到哪去更重要

有了状态定义，下一步就是考虑转移方程。对于当前格子 (i, j)，由于你只能从上方 (i-1, j) 或者左方 (i, j-1) 走过来，所以到达 (i, j) 的路径总数，就是到达这两个格子的路径总数之和：

dp[i][j] = dp[i-1][j] + dp[i][j-1]

这就是整道题最核心的公式。你可能觉得这也太简单了，但我要提醒你一个隐蔽的点：转移方向。很多人写动态规划的时候，习惯性去想“从当前格子可以走到哪里”，然后写出一堆“往后推”的逻辑。但动态规划的核心思维是“当前状态从哪里来”，是倒着想的。这个思维差异很重要。正向推也可以做，遍历顺序反着写就行，但新手阶段我强烈建议统一用“从哪里来”的视角，不容易漏状态、不容易乱。

再补一句：这道题里你只需要向右和向下走，所以不会有回头路，这意味着图是天然的“有向无环图”，按从左到右、从上到下的顺序遍历，每个格子的依赖都一定先被计算出来。这也是为什么动态规划能在这里成立。如果允许上下左右乱走，那就不是计数问题而是图搜索问题了，动态规划也未必适用。

3.3 初始化：边界值为什么是 1

任何动态规划题都有边界条件，这道题的边界条件非常直观：第一行 dp[0][j] 的任意位置，都只有一种走法能到达——就是一路向右走；同理，第一列 dp[i][0] 的任意位置，也只有一种走法——一路向下走。

所以初始化就是：把 dp 数组的第一行和第一列全部填成 1。严谨一点说：

• dp[0][j] = 1，对所有 0 <= j < m
• dp[i][0] = 1，对所有 0 <= i < n

这一步经常被忽略，但它的重要性不亚于转移方程本身。我自己踩过的一个坑是：把起点 dp[0][0] 设成 0，结果整个数组后面全错了。你仔细想想，机器人一开始就在起点，到达起点的路径只有一种，就是“什么都不做”，所以 dp[0][0] 必须等于 1。这是个很小的细节，但能卡住很多人。

3.4 遍历顺序：为什么这样遍历，换顺序行不行

这道题的遍历顺序非常朴素：从左上角开始，一行一行往下扫，每一行里从左往右扫。核心原则只有一个——计算 dp[i][j] 的时候，它依赖的两个格子 dp[i-1][j] 和 dp[i][j-1] 必须已经算完了。

只要你确保这一点，遍历顺序其实可以变。比如说，你可以按列扫，先从左往右一列一列地处理，每一列里从上到下。但如果你先算右下角再算左上角，那就违背了依赖关系，算出来的值全是错的。

有一个小细节值得说一下：在嵌套循环里，外层循环行、内层循环列是最常见的，但这只是因为这样写符合阅读习惯。换成外层循环列、内层循环行同样正确。真正重要的不是循环怎么写，而是“依赖的格子是否先被算出来”这个隐含约束。在你以后遇到带障碍物、带权重、带方向限制的变体题时，这一步的思考会救你很多次。

4. 完整实操：从暴力递归到四套代码的进化之路

理论知识说完了，现在进入实操。我会按“暴力递归（只讲思路）→ 记忆化搜索 → 二维 DP → 滚动数组优化 → 组合数学公式”这个顺序，带着你把代码一步一步进化。每一步都有清晰的代码示范和踩坑记录，你可以直接照着敲。

4.1 暴力递归版本：先让思路跑通

暴力递归的核心逻辑，前面已经说过：定义一个函数 dfs(i, j) 表示从起点到 (i, j) 的路径数，那么 dfs(i, j) = dfs(i-1, j) + dfs(i, j-1)，边界是当 i == 0 或 j == 0 时返回 1。代码写出来是这样的：

def dfs(i, j): # 边界：第一行或第一列只有一种走法 if i == 0 or j == 0: return 1 return dfs(i - 1, j) + dfs(i, j - 1) def unique_paths_dfs(n, m): return dfs(n - 1, m - 1)

这个版本能出正确结果，但只能处理很小的 n、m，比如 5 乘 5、7 乘 7 这种。一旦到 15 乘 15，等待你的就是漫长到让人怀疑人生的运行时间。我在实际练习的时候，用这个版本跑过 18 乘 18，大概跑了半分钟，21 乘 21 直接等到崩溃。

为什么？可以用一棵递归树来解释：dfs(3, 3) 调用了 dfs(2, 3) 和 dfs(3, 2)，而这两个又会共同调用 dfs(2, 2)，子问题被重复计算，导致整体时间复杂度是 O(2^(n+m)) 级别的指数爆炸。

4.2 记忆化搜索：给递归加一个缓存

既然重复计算是罪魁祸首，那最直接的优化就是加缓存。把已经算过的 dfs(i, j) 存起来，下次再要直接查表，不再往下递归。这就是记忆化搜索，也叫自顶向下的动态规划。

from functools import lru_cache @lru_cache(None) def dfs(i, j): if i == 0 or j == 0: return 1 return dfs(i - 1, j) + dfs(i, j - 1) def unique_paths_memo(n, m): return dfs(n - 1, m - 1)

加了这一行缓存之后，每个 (i, j) 只会被计算一次，时间复杂度和空间复杂度都降到了 O(n*m)。这就是动态规划的雏形——虽然它没有显式地写数组，但本质上是“用空间换时间”的思想。

我个人很喜欢记忆化搜索，因为它写起来非常接近人类直觉，不需要想遍历顺序。很多复杂动态规划题，尤其是区间 DP 或者树形 DP，直接用记忆化搜索反而比递推 DP 好写得多。但面试的时候，如果你能主动给出从暴力到记忆化再到 DP 的演进路径，会显得你对整个思路的理解非常清晰。

4.3 经典二维 DP：面试最常写的版本

记忆化搜索虽然直观，但它有递归调用栈的额外开销，而且 Python 的递归深度限制在某些极端情况下也会成为问题。面试官多半会希望你写出显式的递推版 DP，也叫自底向上的动态规划。这一步，我们把思路从“从终点往前递归”切换成“从起点往后递推”。

def unique_paths_dp(n, m): # 初始化一个 n 行 m 列的全 0 二维数组 dp = [[0] * m for _ in range(n)] # 第一列只有一种走法 for i in range(n): dp[i][0] = 1 # 第一行只有一种走法 for j in range(m): dp[0][j] = 1 # 逐行逐列填表 for i in range(1, n): for j in range(1, m): dp[i][j] = dp[i-1][j] + dp[i][j-1] return dp[n-1][m-1]

代码本身不难，但有几个细节值得你注意。第一是创建二维数组的方式，Python 里[[0] * m] * n是错误示范，因为这样每一行其实是同一个列表的引用，改一行全跟着变，必须用列表推导式[[0] * m for _ in range(n)]。第二是循环的起点，从 1 开始，因为边界第 0 行和第 0 列已经在初始化时被填好了。第三是返回值，dp[n-1][m-1]就是右下角的路径总数，千万别手滑写成dp[m-1][n-1]，这种低级错误我见过不止一次。

为了让你确认自己写对了，我放一个 3 行 3 列的 dp 表填充结果：

右下角是 6，也就是 3 乘 3 网格的答案。你自己用手推一遍这个表，能顺下来就说明这道题真的理解了。

4.4 滚动数组优化：空间复杂度从 O(n*m) 降到 O(m)

二维 DP 已经足够应付大多数场景了，但如果你去刷题，可能会看到空间优化的版本。这里有一个非常优雅的观察：计算第 i 行的 dp 值，只用到第 i-1 行的数据，再往上的行就再也用不到了。所以不需要保留整个二维表，只需要保留一行就够了。

这就是传说中的滚动数组。代码如下：

def unique_paths_optimized(n, m): # 只保留一行状态 dp = [1] * m # 从第二行开始逐行更新 for i in range(1, n): for j in range(1, m): dp[j] = dp[j] + dp[j-1] return dp[m-1]

这段代码看似简单，很多人第一次看会懵：dp[j] + dp[j-1] 里的 dp[j] 和 dp[j-1] 分别代表什么？其中 dp[j] 在更新前，是上一行同一列的值，也就是“从上方来的路径数”；dp[j-1] 在更新后，是当前行左边格子的值，也就是“从左方来的路径数”。两者相加，正好就是当前格子的路径总数。

这个优化能把空间复杂度从 O(n*m) 降到 O(m)。如果题目同时要求 n 和 m 很小，这不算什么，但当网格变大，比如 10000 乘 10000，显式开辟一个亿级元素的二维数组就很不现实，滚动数组就非常实用了。

我在实际教学里发现，有不少同学能理解二维 DP，但看不懂滚动数组。我给他们建议是：不要“读”这段代码，而是拿笔在纸上画一个只有一行的表格，把每次循环更新后数字的变化过程写出来，多写两轮就恍然大悟了。空间优化是最容易出 bug 的地方，核心理解点在于“更新时机”。

4.5 组合数学解法：这道题的另一种身份

这道题本质上和组合数学是相通的。我们前面说过，机器人一共要走 n + m - 2 步，其中向下走 n - 1 步，向右走 m - 1 步。路径总数为从这 n + m - 2 步中选出 n - 1 步作为向下走的组合数，也就是 C(n + m - 2, n - 1)。

用 Python 可以直接这样写：

import math def unique_paths_math(n, m): return math.comb(n + m - 2, n - 1)

时间复杂度可以做到 O(min(n, m))，空间复杂度 O(1)，比动态规划更快更省。但你要注意，这个解法只适用于“没有任何障碍物”的纯粹版题目。一旦题目加了障碍物，组合数公式就不能直接套了，这时候动态规划才是通用解法。

那为什么还要学动态规划，直接用组合数不香吗？因为这道题是动态规划练手的敲门砖，你的目标不是只解决这一道题，而是通过它掌握一种能解决一大类问题的思维工具。面试官想考察的也不是你会不会算组合数，而是你有没有能力把一个看似复杂的问题转化成子问题逐步求解。

5. 常见问题与排查技巧：我踩过的坑都在这里

这一节是我最想写的内容。网上各种教程都在讲“怎么写对”，但很少讲“写错了怎么排查”。我把这些年刷题和带新人过程中最常见的错误整理成了一份速查表，每一个都是真人真事。

5.1 溢出问题：小方格也会撑爆整数范围

这道题看起来就是几十、几百的数字，很多人根本不会想到溢出问题，但真实情况是：一个稍微大一点的网格，路径数会涨得超乎你想象。

我算过几个具体数字：

• 10 行 10 列：48620 条
• 15 行 15 列：40116600 条
• 20 行 20 列：35345263800 条
• 25 行 25 列：16123801841550 条
• 30 行 30 列：30067266499541040 条

30 行 30 列的时候，答案已经超过 3 千万亿了。如果用 C++ 写，int 类型 4 字节，最大才 21 亿左右，跑到 15 行左右就开始溢出。Java 的 int 也一样。C++ 要用 long long，Java 要用 long，因为 25 行 25 列的答案超过 16 万亿，37 行 37 列的答案超过 9 千亿亿，连 long long 都快撑不住。Python 在这一点的优势是巨大的，整数可以无限大，不用考虑溢出。

我建议你在刷这道题之前，先去查一下目标语言里每种整数类型的范围，然后问自己一句：n 和 m 最大可能是多少？如果题目没有给范围，拿 long 是最稳妥的选择。

5.2 1x1、1xn、nx1 的边界情况你敢拍胸脯吗

一道题的正确性，不仅体现在常规数据上，更体现在边界数据上。很多隐性 bug 都是在边界处暴露的。

• 1 行 1 列：只有 1 个格子，起点就是终点，路径数为 1。用 DP 跑一遍，dp[0][0] 初始化为 1，返回 1，没问题。
• 1 行 n 列：只能一直向右走，只有一条路径。dp 数组第一行全为 1，返回 1，没问题。
• n 行 1 列：同理，只有一条路径。

这些边界情况看着简单，但如果你在初始化时把 dp[0][0] 漏掉了，或者在返回写错了行列下标，哪怕题目给的范围是 1 <= n, m <= 100，你的答案也会偏移。所以写完代码后，第一件事就是用边界用例自测三连：1x1、1x100、100x1。

还有一个小技巧：题目里如果 n 和 m 可以等于 0，本质上就是空网格，这时候应该返回 0 而不是 1。虽然大多数题不会这么出，但你多考虑一层，写出来的代码就多一分健壮性。

5.3 调试技巧：把 dp 表打出来，比什么 log 都管用

我在调试动态规划题的时候有一个习惯：跑完循环之后，把整个 dp 表 print 出来看一遍。这个习惯帮我发现了无数次灵异 bug。

举个例子，如果你写的是二维 DP，可以加一行调试代码：

for row in dp: print(row)

看输出结果是否符合预期。以 3 行 3 列为例，正确的表应该是第一行和第一列全 1，中间按“上 + 左”递推。如果你的表中出现了类似 [1, 1, 1], [1, 2, 3], [1, 3, 9] 这样的结果，说明问题出在循环内部——右下角的 9 意味着你把 dp[i][j-1] 和 dp[i-1][j] 乘起来了，而不是相加。

可视化调试对我来说就像给程序照 X 光，比任何断点调试都要直观。如果你遇到滚动数组版本看起来总是不对，也建议先回到二维 DP 版本打印出完整表格，确认逻辑无误后，再手动追踪一遍滚动数组的每一步更新。新手最忌讳的就是在版本之间跳来跳去却从不打印中间结果。

5.4 审题坑：坐标从 0 开始还是从 1 开始

还有一个容易被忽略的坑是坐标系的歧义。有的题描述会说“位于第 1 行第 1 列”，这时候如果你直接拿数组下标 0 去对齐，初始化部分会出问题。遇到这类输入，建议在代码开头先做一步坐标转换，把 1-based 的输入转成 0-based，避免后续大量 +1、-1 的混淆。

我自己的习惯是：状态定义里写清楚“dp[i][j] 表示从起点到达第 i 行第 j 列”，然后无论输入是什么形式，第一步统一减一。这样思路不容易乱，歧义只存在于一处，而不是散落在整个代码里。

6. 从一道题到一类题：这个模板能打多少变体

动态规划最迷人的地方，不在于你会用这个套路解这一道题，而在于“状态定义 + 转移方程 + 初始化 + 遍历顺序”这四板斧换着花样能打下一大片题目。这道 n*m 方格前进题，就是那个最好的出发点。

6.1 变体一：带障碍物的路径数

如果网格里某些格子有障碍物，不能走，怎么办？转移方程几乎不用大变：只要当前格子是障碍物，就令 dp[i][j] = 0；否则还是 dp[i][j] = dp[i-1][j] + dp[i][j-1]。初始化时也要注意：如果第一行或第一列里有一个障碍物，那它后面所有的格子都到不了了，都应该保持 0。

核心区别就一句话：正常情况下“上方值加左方值”，碰到障碍物直接置零。很多刚学完基础版的同学，做这道变体时会被“边界行遇到障碍物”搞晕。最稳妥的理解方式是：障碍物把它所在的行和列切断了，所有依赖它的格子全部失效。拿 1 行 4 列、第 2 列是障碍物来举例，结果应该是 [1, 0, 0, 0]，第 3 列第 4 列都到不了。

6.2 变体二：找一条最小路径和

如果把“计数”改成“求最小路径和”，每一格还有一个权重值，这就是 LeetCode 第 64 题。转移方程变成：dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])，意思是到当前格子的最小代价，等于当前格子的代价加上从上方或左方过来的较小代价。

这次的初始化思路也不一样：第一行只能从左往右累加，第一列只能从上往下累加。从这个变体你能明显感受到，动态规划的四步框架完全没变，变的只是“转移方程里是加号还是取 min”这一处细节。

6.3 变体三：不只求数量，还要输出完整路径

如果题目要求你输出每一条路径，这就要回到回溯/DFS 的思路，因为路径数量可能是指数级的，不可能用动态规划直接生成所有路径。动态规划的价值在于快速求得数量，而回溯的价值在于枚举具体方案。两种方法各有适用场景，理解它们的分工，比盲目背模板重要得多。

我在实际面试中见过一个很有意思的追问：“既然你已经知道有多少条路径了，能不能反向推出其中某一条？”这时候你可以从终点倒推，如果 dp[i-1][j] 大于 dp[i][j-1]，说明到达当前格子的路径更多来自上方，就往回走到上方，不断回溯直到起点，就能还原出一条路径。这种“倒推路径”的思路，在很多动态规划题里都有用，比如最长公共子序列的输出。

6.4 变体四：不同起点和终点的大网格

还有一类题，不是从 (0,0) 走到 (n-1,m-1)，而是给定多个起点和终点，问你某两点间有多少条路径。做法是在 dp 表上做 mark，把所有起点初始化为 1，然后按同样规则递推，终点处取值就是答案。本质上，动态规划表的信息是可以复用的，提前算好一整张表，后续任何查询都可以 O(1) 完成。

所以你现在应该能理解，为什么那么多算法博主都说“动态规划是一种思想，不是一道题”。方格前进这道题，就是你进入这个思想的第一个台阶。

7. 我个人在实际操作中的一点体会

写了这么多，最后聊几句题外话。

如果你刚接触动态规划，我建议你千万不要只抄代码。拿到这道题，先自己画一个 5 乘 5 的表格，用手推一遍 dp 值；再用暴力递归写一遍（哪怕慢，也要跑通）；然后加记忆化；最后改成滚动数组。这个过程完整走下来，你对动态规划的“重叠子问题”和“空间换时间”会有非常直观的感受。我见过太多人刷题只求“AC”，代码是抄来的，思路是背的，结果换一道题又不会了。

另外一个很实用的建议：多问自己“为什么”。为什么 dp[i][j] 是上方加左方，而不是上方乘左方？为什么边界是 1 而不是 0？为什么滚动数组更新时 dp[j-1] 已经是当前行而不是上一行？这些“为什么”每个都值得花时间去想清楚。想通一个，比你多刷十道题更有用。

最后再分享一个小技巧：这道题的滚动数组优化版本，代码只有几行，特别适合拿来当默写题，用来检验自己在面试高压环境下还记不记得动态规划的核心框架。如果面试紧张到只能写出二维 DP 版本，也没关系，先答对再谈优化，一步一步来，面试官更看重你的思考过程，而不是最终答案。