62. 不同路径

难度：🟡 Medium | 标签：动归、组合数学 | 状态：⬜ LeetCode 链接

思路

dp[i][j] = dp[i-1][j] + dp[i][j-1]。 首行 / 首列全 1。

滚动数组：一维 dp[j] = dp[j] + dp[j-1]，正向更新。

代码

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

复杂度

• 时间 O(m · n)，空间 O(n)

易错 / 回顾

• 数学解：C(m+n-2, m-1)，O(min(m, n))
• 滚动数组方向：本题正向（依赖上方和左侧，都是新一行的旧值）
• 63（带障碍）：障碍位置 dp = 0