不同路径问题如何用动态规划求解？（LeetCode 62）

简化版

一个 m×n 网格，机器人从左上角走到右下角，每次只能向右或向下，问有多少条不同路径。设 dp[i][j] 为「走到格子 (i,j) 的路径数」，因为只能从上面或左边过来，所以 dp[i][j] = dp[i-1][j] + dp[i][j-1]。第一行、第一列只有一条路（一直向右 / 一直向下），初始化为 1。答案 dp[m-1][n-1]。可压成一维数组，也有组合数公式 C(m+n-2, m-1)。

详细版

int uniquePaths(int m, int n) {
    int[] dp = new int[n];
    Arrays.fill(dp, 1);              // 第一行：只有 1 条路径
    for (int i = 1; i < m; i++) {
        for (int j = 1; j < n; j++) {
            dp[j] += dp[j - 1];      // 新 dp[j](下面来) = 旧 dp[j](上面) + dp[j-1](左边)
        }
    }
    return dp[n - 1];
}

状态：dp[i][j] = 到达格子 (i,j) 的不同路径数。
转移方程：dp[i][j] = dp[i-1][j] + dp[i][j-1]（从上或从左而来）。
初始化：第一行、第一列全为 1（只能沿边直走，唯一路径）。
一维压缩：dp[j] += dp[j-1]——等号右边的 dp[j] 是上一行留下的值（上方），dp[j-1] 是本行刚更新的（左方）。
复杂度：DP 为 O(m·n) 时间、O(n) 空间。

完整版教学

一、问题与网格 DP

不同路径：m×n 的网格，从左上角 (0,0) 到右下角 (m-1,n-1)，每步只能向右或向下，求路径总数。这是网格 DP（二维 DP） 的入门代表——很多「矩阵里从一角走到另一角」的题都套这个框架（最小路径和、带障碍的不同路径等）。

之所以能按行或按列填表，是因为移动方向只有向右和向下，状态依赖形成有向无环图。若允许向左或向上，路径可能形成环，“上方加左方”的拓扑顺序就不再覆盖全部合法路径。

二、状态定义与转移（从上或从左来）

定义状态：dp[i][j] = 「从起点走到格子 (i,j) 的不同路径数」。

转移方程——盯住「到 (i,j) 的最后一步从哪来」。因为只能向右或向下走，所以到达 (i,j) 前的那一格，只可能是：

它上面的 (i-1, j)（最后一步向下）；
它左边的 (i, j-1)（最后一步向右）。

这两种走法不重叠、且穷尽所有可能，于是路径数相加：

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

三、初始化：第一行、第一列都是 1

转移方程需要「上面」和「左边」，所以第一行（没有上面）和第一列（没有左边）要单独初始化：

第一行任意 (0, j)：只能从起点一路向右走到，唯一一条路径 → dp[0][j] = 1。
第一列任意 (i, 0)：只能一路向下走到，也唯一 → dp[i][0] = 1。

把边界铺成 1 之后，其余格子用转移方程从左上往右下逐个填，答案在 dp[m-1][n-1]。

四、滚动数组压成一维

观察 dp[i][j] = dp[i-1][j] + dp[i][j-1]：算当前行时，只需要上一行的同列值和本行左边的值。所以可以只留一维数组 dp[j]，按行从上往下、每行从左往右更新：

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

更新前的 dp[j] 恰好是上一行的 dp[i-1][j]（还没被这一行覆盖），dp[j-1] 是本行刚算好的左邻 dp[i][j-1]，两者相加正好是新的 dp[i][j]。空间从 O(m·n) 降到 O(n)。

五、组合数学解法 C(m+n-2, m-1)

这题还有 O(m+n) 的纯数学解。从左上到右下，总共要走 m-1 步向下、n-1 步向右，一共 (m-1)+(n-1) = m+n-2 步。一条路径就是这串「下/右」步骤的一个排列，本质是从 m+n-2 步里选出哪 m-1 步向下（其余自动是向右），所以路径数就是组合数：

C(m+n-2, m-1)

它比 DP 更快，但一旦网格里有障碍物（LeetCode 63），组合公式就失效了，只能回到 DP（把障碍格的 dp 置 0）。所以 DP 是更通用的解法，组合公式是本题无障碍时的特例优化。

六、状态语义、转移来源与遍历顺序

本题状态的完整含义是：dp[r][c] 表示到达格子 (r,c) 的路径数，最后一步只可能来自上方或左方。

转移过程是：dp[r][c]=dp[r-1][c]+dp[r][c-1]；一维压缩时 dp[c] 更新前是上方，dp[c-1] 是左方。写代码前应逐个解释转移候选对应题目中的哪种最后选择，并确认这些候选互斥且覆盖全部可能。

定义状态：它概括哪段输入、处于什么决策阶段
列出选择：当前答案的最后一步有哪些来源
写出转移：由已计算的前驱组合当前答案
确定顺序：使用前驱之前不能覆盖它

数字推演：3×7 网格需走 2 次下、6 次右，共 8 步，选择 2 个下移位置得到 C(8,2)=28。

记忆钩子：DP 最容易错的不是 max/min，而是状态少记了信息或一维压缩后读到了本轮新值。

七、初始化、空间压缩与适用边界

实现边界是：首行首列在无障碍时为 1；有障碍时遇阻置 0，不能继续沿用；组合公式中间乘除要防溢出。

核对项	本题答案
复杂度	DP O(mn) 时间、O(n) 空间；无障碍组合数学 O(min(m,n)) 时间
基本状态	必须能直接解释为规模 0 或最小输入的真实含义
遍历顺序	由转移依赖决定，不能为了习惯随意正序/倒序
空间压缩	仅在被覆盖状态之后不再需要时安全
结果位置	可能是最后状态、全局最大值或多个终态的聚合

测试应覆盖空/最小输入、不可达状态、全零或负值、答案刚好发生在边界，以及会区分正序与倒序的样例。若需要恢复方案，不能只保留压缩后的数值，还要记录前驱或保留完整状态表。

八、常见误区与追问

误区：第一行第一列都初始化 0。 起点到边界只有一条连续走法，应为 1。
误区：一维 dp 每行要重新清零。 旧 dp[c] 正好代表上方路径数，不能清零。
误区：组合数直接算阶乘最安全。 阶乘很快溢出，应边乘边除或用大整数。
追问：为什么没有后效性？ 到当前格后的未来只与位置有关，与具体路径无关。
追问：有障碍怎样转移？ 障碍格设 0，其他格仍累加上和左。
追问：若可向四方向走怎么办？ 可能形成环，简单网格 DP 的拓扑顺序不再成立。

九、加强记忆

不同路径是网格 DP：dp[i][j] = 到 (i,j) 的路径数，只能从上或左来 → dp[i][j]=dp[i-1][j]+dp[i][j-1]。第一行第一列初始化为 1（沿边直走唯一路径），答案 dp[m-1][n-1]。可用一维滚动数组 dp[j]+=dp[j-1]（上方 + 左方）压到 O(n) 空间。无障碍时有组合数捷径 C(m+n-2, m-1)（下/右步骤的排列），有障碍则必须用 DP。

简化版

详细版