LeetCode 62. 不同路径

◎

本节目标

用上方和左方的路径数递推计算单向网格中的不同路径数。

返回网格与路径动态规划框架

查看 LeetCode 原题

题意与约束

从 m×n 网格左上角到右下角，每步只能向右或向下，求不同路径数。

第一反应与重复子问题

到同一格的所有路径，最后一步必来自上方或左方；枚举所有移动序列会重复计算相同终点。

状态定义与转移推导

dp[r][c] 为到达该格的路径数，dp[r][c]=dp[r-1][c]+dp[r][c-1]。一维时 dp[c] 先代表上方，加上已更新的 dp[c-1] 即左方。

正确性依据

上、左两类最后一步互斥且覆盖全部合法路径，因此相加恰好得到总数。

样例执行过程

3×3 中首行、首列均为 1，中间依次为 2、3、3、6，答案 6；单行始终只有一条路径。

代码实现

C++

C++17

#include <vector>
using namespace std;

class Solution {
public:
    int uniquePaths(int m, int n) {
        vector<int> dp(n, 1);
        for (int row = 1; row < m; row++) {
            for (int col = 1; col < n; col++) {
                dp[col] += dp[col - 1];
            }
        }
        return dp[n - 1];
    }
};

Python

Python 3

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        dp = [1] * n
        for _ in range(1, m):
            for col in range(1, n):
                dp[col] += dp[col - 1]
        return dp[-1]

复杂度分析

时间 O(mn)，空间 O(n)。

边界与易错点

• 单行或单列答案为 1。
• 初始数组全为 1 才能表达首行路径。
• 不要把 m、n 当作最后下标。

模式迁移

加入障碍物时把障碍格路径数设为 0；改为最小代价时把加法换为最小值转移。