#62
中等
低频
动态规划不同路径
这是一道围绕图展开的高频练习。建议先掌握「动态规划」这套写法，再结合下方步骤讲解理解状态维护、边界处理和复杂度取舍。
图
题目分析
这道题表面上是在处理「不同路径」，但先要想清楚题目到底让你返回什么，以及过程中哪些约束必须一直满足。从题型上看，它主要在考 图 这些能力。这类题先别急着写转移式，先定义清楚状态表示什么，再看它如何由前面的状态推出。只有先把题目要求翻译成人话，后面的推荐代码才是在实现思路，而不是直接给答案。
接下来怎么看推荐代码： 带着这个理解再看推荐代码时，重点观察这条主线：到每个格子的路径数等于上方路径数加左方路径数。
推荐代码
推荐解法：动态规划
时间复杂度： O(m*n)
空间复杂度： O(m*n)
核心思路： 到每个格子的路径数等于上方路径数加左方路径数。
class Solution {
public int uniquePaths(int m, int n) {
// 创建一个m行n列的二维数组
int[][] dp = new int[m][n];
// 初始化第一行，所有元素都为1
for (int i = 0; i < n; i++) {
dp[0][i] = 1;
}
// 初始化第一列，所有元素都为1
for (int i = 0; i < m; i++) {
dp[i][0] = 1;
}
// 从(1,1)开始遍历所有网格
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 来计数路径数量。
核心过程
- 定义状态为到每个格子的路径条数。
- 第一行和第一列都初始化成 1。
- 内部格子由上方和左方路径数相加得到。
- 最终右下角就是答案。
复杂度总结
时间复杂度 O(m*n)，空间复杂度 O(m*n)。
面试补一句：这题是网格 DP 最基础的“上左求和”模板。
核心思路
不同路径是最标准的网格计数 DP。因为机器人只能向右或向下走，所以每个位置的路径数只来自上方和左方两种来源。
步骤讲解
1
定义到每个格子的路径数
令 dp[i][j] 表示从起点走到 (i,j) 的不同路径数。
为什么这样做：终点答案自然落在右下角。
对应代码提示：int[][] dp = new int[m][n];
2
初始化第一行和第一列
第一行和第一列只有一种走法，因此全为 1。
为什么这样做：边界格子没有来自两个方向的选择。
对应代码提示：dp[i][0] = 1; dp[0][j] = 1;
3
内部格子取上方加左方
对其余位置，路径数等于上边路径数和左边路径数之和。
为什么这样做：到当前格子最后一步只可能来自这两个方向。
对应代码提示：dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
易错点
把最短路径和路径数量混淆
这题是计数，不是求最小代价。
正确理解：状态转移用加法，不是 min/max。
边界初始化为 0
会导致整张表都推不起来。
正确理解：第一行第一列必须初始化为 1。
忘记题目不含障碍
这题边界条件比带障碍版本更简单。
正确理解：转移只需看上和左，不用额外判障碍。
复杂度与适用判断
时间复杂度：O(m*n)
空间复杂度：O(m*n)
比其他方案更好在哪里：比 DFS 穷举路径高效太多。
适用判断：网格题若求路径条数且移动方向固定，优先考虑二维 DP。
额外提醒
- “上方 + 左方”是这类网格计数题的标准模板。
动画演示
如果你还没完全看懂，可以展开动画演示。
动态规划动画演示
想看这段解法是怎么一步步运行的，可以展开动画继续观察。
动态规划动画演示
想看这段解法是怎么一步步运行的，可以展开动画继续观察。
准备就绪 - 输入网格的行数和列数，然后点击开始
动画演示仅在桌面端提供，移动端请优先阅读推荐代码与结构化讲解。