题目

思路

一句话：走到某格只能来自上方或左方，所以该格的路径数 = 上方格子的路径数 + 左边格子的路径数。

先想最直白的：从左上角出发做 DFS，每一步分「向右、向下」两叉，走到右下角就记一条。这样能算对，但路径总数是组合数级别——对 m = n = 100，路径数是天文数字，枚举完全不可行。

关键观察：到格子 (i, j) 的路径，可以按最后一步分成互不重叠的两类：

• 最后一步从上方 (i−1, j) 走下来；
• 最后一步从左边 (i, j−1) 走过来。

这两类合起来覆盖了所有到 (i, j) 的路径，所以直接把两个数相加即可：dp[i][j] = dp[i−1][j] + dp[i][j−1]。

边界也好定：第一行的格子只能一直向右，第一列的格子只能一直向下，因此它们的路径数都是 1。

于是选定做法：自底向上的网格 DP。先把第一行、第一列填成 1，再按从上到下、从左到右的顺序填内部格子；每个格子只依赖上方和左方，填的时候这两个值都已经算好了。

解法

用一张 m×n 的表 dp，dp[i][j] 表示从左上角走到 (i, j) 的路径数：

1. 初始化：第一行、第一列全部为 1。
2. 从 i = 1、j = 1 开始，逐个计算 dp[i][j] = dp[i−1][j] + dp[i][j−1]。
3. 返回右下角 dp[m−1][n−1]。

以 m = 3、n = 3 为例，填表过程如下：

右下角的值 6 就是答案。下面 C++ 给出二维版，Python 给出滚动数组版——两者是同一个转移，只是空间占用不同。

下图把上面 3 个步骤串成流程，并逐步演示：

C++

class Solution {
public:
 int uniquePaths(int m, int n) {
 vector<vector<int>> dp(m, vector<int>(n, 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];
 }
 }
🔒
本篇为付费内容
您已阅读试读部分，购买后即可解锁全文。
⚠️ 本站内容已做唯一性标记并受版权保护，未经授权禁止转载，侵权必究。