62. 不同路径#

大家好！今天我们要一起探索一道经典题目：不同路径。这道题不仅本身很有趣，更重要的是，它是理解多维动态规划的绝佳入门题目。让我们一起开启这段从一维思维到多维思维的探索之旅！

🌟 从一维到多维：思维的升级#

在开始今天的题目之前，让我们先理解一下什么是多维动态规划，以及为什么需要它。

一维动态规划回顾#

在之前的题目中，我们接触过很多一维动态规划问题：

爬楼梯：dp[i]表示爬到第i阶的方法数
最大子数组和：dp[i]表示以第i个数结尾的最大和
打家劫舍：dp[i]表示偷到第i个房子时的最大金额

这些问题的共同特点是：状态只和”一个变量”有关。

为什么需要多维？#

现实生活中，很多问题需要考虑多个因素：

背包问题：需要考虑物品数量和总重量两个维度
编辑距离：需要考虑两个字符串的长度
今天的题目：需要考虑横坐标和纵坐标

问题描述#

题目目标#

一个机器人位于一个 m x n 网格的左上角，每次只能向下或者向右移动一步。机器人试图到达网格的右下角。请问总共有多少条不同的路径。

示例 1#

输入： m = 3, n = 7 输出： 28 说明： 把输入和输出放在一起看，会更容易直接抓住题目要求的变化。

🎯 问题描述：机器人走格子#

一个机器人位于一个 m x n 网格的左上角，每次只能向下或者向右移动一步。机器人试图达到网格的右下角，问总共有多少条不同的路径？

例如：

输入：m = 3, n = 2
输出：3
解释：从左上角开始，总共有 3 条路径可以到达右下角。
1. 向右 → 向下
2. 向下 → 向右
3. 向右 → 向下

plaintext

🤔 从小例子开始思考#

让我们从最简单的例子开始：

2 x 2 的网格：

起点 →  ○
 ↓     ↓ 
 ○  →  终点

可能的路径：
1. 右→右→下
2. 右→下→右
3. 下→右→右

答案是2条路径

plaintext

再看一个3 x 2的例子：

3 x 2 的网格：

起点 →  ○
 ↓     ↓ 
 ○  →  ○
 ↓     ↓
 ○  →  终点

路径1：右→下→下
路径2：下→右→下
路径3：下→下→右

答案是3条路径

plaintext

💡 发现规律：多维思维的突破#

仔细观察这些例子，我们发现一个重要规律：

要到达某个点(i,j)，只能从：

上面的点(i-1,j)向下走一步
左边的点(i,j-1)向右走一步

这就是我们的状态转移方程！

📝 二维动态规划解法#

状态定义：

dp[i][j] 表示：从起点到位置(i,j)的不同路径数

状态转移方程：

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

class Solution {
    public int uniquePaths(int m, int n) {
        // dp[i][j] 表示：从起点 (0,0) 走到位置 (i,j) 的不同路径总数
        int[][] dp = new int[m][n];

        // 初始化第一行：机器人只能一直向右走，因此每个位置都只有 1 条路径
        for (int j = 0; j < n; j++) {
            dp[0][j] = 1;
        }

        // 初始化第一列：机器人只能一直向下走，因此每个位置都只有 1 条路径
        for (int i = 0; i < m; i++) {
            dp[i][0] = 1;
        }

        // 从第二行第二列开始填表（i=1、j=1），因为第一行和第一列已初始化完毕
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                // 到达 (i,j) 只能来自上方 (i-1,j) 或左方 (i,j-1)
                // 因此路径总数 = 上方路径数 + 左方路径数
                dp[i][j] = dp[i-1][j] + dp[i][j-1];
            }
        }

        // 右下角 (m-1,n-1) 存的就是最终答案
        return dp[m-1][n-1];
    }
}

java

🎨 图解二维DP的执行过程#

以3x3网格为例：

1. 初始化第一行和第一列：
   1  1  1
   1  □  □
   1  □  □

2. 填充(1,1)位置：
   1  1  1
   1  2  □
   1  □  □
   解释：可以从上面(1)或左边(1)过来，所以是1+1=2

3. 填充(1,2)位置：
   1  1  1
   1  2  3
   1  □  □
   解释：可以从上面(1)或左边(2)过来，所以是1+2=3

... 依此类推

最终得到：
   1  1  1
   1  2  3
   1  3  6

plaintext

💫 空间优化：降维打击#

由于每个位置只依赖于上面和左边的值，我们可以只用一维数组：

class Solution {
    public int uniquePaths(int m, int n) {
        // 一维 dp：dp[j] 表示“当前处理到的这一行”中，到达第 j 列的路径数
        int[] dp = new int[n];

        // 初始化为 1：对应二维 dp 的第一行（只能从左往右走）
        Arrays.fill(dp, 1);

        // 从第 2 行开始处理（下标 1）
        for (int i = 1; i < m; i++) {
            // 从第 2 列开始更新（下标 1），dp[0] 始终为 1（第一列只能向下）
            for (int j = 1; j < n; j++) {
                // dp[j] 更新前代表“上一行同列”的路径数（上方）
                // dp[j-1] 是“当前行前一列”的路径数（左方）
                // 二者相加后得到当前位置的新路径数
                dp[j] += dp[j-1];
            }
        }

        // 最后一列即右下角的路径总数
        return dp[n-1];
    }
}

java

🎯 多维动态规划的特点#

状态的定义：
- 一维：dp[i]只需要一个变量
- 多维：dp[i][j]需要多个变量共同确定状态
状态转移：
- 一维：通常只需要考虑前面的某些状态
- 多维：需要考虑多个维度上的前序状态
初始化：
- 一维：通常只需要初始化几个值
- 多维：可能需要初始化多个维度的边界值
遍历顺序：
- 一维：通常从小到大遍历
- 多维：需要考虑多个维度的遍历顺序

💡 解题技巧#

画图理解：多维问题一定要画图
找依赖关系：搞清楚当前状态依赖哪些之前的状态
考虑边界：多维问题的边界条件很重要
空间优化：看是否可以降维处理

🎓 面试指南#

遇到多维动态规划问题时，建议这样思考：

先用最小的例子理解问题
画图确定状态之间的依赖关系
找出状态转移方程
考虑如何初始化
最后考虑是否可以优化空间

🔍 相似题目#

最小路径和
不同路径 II（有障碍物）
三角形最小路径和

🤔 思考题#

如果要打印出所有可能的路径，该如何修改代码？

多维动态规划看起来复杂，但只要我们理解了状态的定义和转移关系，就能用同样的思维方式解决更多的问题。希望这篇文章能帮助你构建起解决多维动态规划问题的思维框架！