不同路径：从一维到多维的思维跃迁

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

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

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

一维动态规划回顾

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

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

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

为什么需要多维？

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

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

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

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

例如：

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

🤔 从小例子开始思考

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

2 x 2 的网格：

起点 →  ○
 ↓     ↓ 
 ○  →  终点

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

答案是2条路径

再看一个3 x 2的例子：

3 x 2 的网格：

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

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

答案是3条路径

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

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

要到达某个点(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数组
        int[][] dp = new int[m][n];
        
        // 初始化第一行
        for (int j = 0; j < n; j++) {
            dp[0][j] = 1;
        }
        
        // 初始化第一列
        for (int i = 0; i < m; i++) {
            dp[i][0] = 1;
        }
        
        // 填充dp数组
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[i][j] = dp[i-1][j] + dp[i][j-1];
            }
        }
        
        return dp[m-1][n-1];
    }
}

🎨 图解二维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

💫 空间优化：降维打击

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

class Solution {
    public int uniquePaths(int m, int n) {
        int[] dp = new int[n];
        Arrays.fill(dp, 1);
        
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[j] += dp[j-1];
            }
        }
        
        return dp[n-1];
    }
}

🎯 多维动态规划的特点

1. 状态的定义：

   • 一维：dp[i]只需要一个变量
   • 多维：dp[i][j]需要多个变量共同确定状态

2. 状态转移：

   • 一维：通常只需要考虑前面的某些状态
   • 多维：需要考虑多个维度上的前序状态

3. 初始化：

   • 一维：通常只需要初始化几个值
   • 多维：可能需要初始化多个维度的边界值

4. 遍历顺序：

   • 一维：通常从小到大遍历
   • 多维：需要考虑多个维度的遍历顺序

💡 解题技巧

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

🎓 面试指南

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

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

🔍 相似题目

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

🤔 思考题

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

---

作者：忍者算法
公众号：忍者算法

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

#算法面试 #LeetCode #动态规划 #多维动态规划