不同路径

GitHub跳转原题关系图返回列表

网格 DP：首行首列初始化为 1，内部 dp[j] += dp[j-1] 即上方加左方。

OJ: leetcodecn

题目 ID: unique-paths

难度:普及-

标签:动态规划组合数学

日期: 2026-07-29 12:49

目录

  1. 题意
  2. 思路
  3. 代码
  4. 复杂度
  5. 总结

题意

从左上到右下，只能向右或向下，求路径数。

思路

dp[j] 表示到达当前行第 j 列的路径数。首行全为 1，每行从左到右 dp[j] += dp[j-1]（上方 + 左方）。空间优化到一维。

代码

cpp
#include <bits/stdc++.h>
using namespace std;

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];
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int m, n;
    cin >> m >> n;
    cout << Solution().uniquePaths(m, n) << '\n';
    return 0;
}
python
#!/usr/bin/env python3
class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        dp = [1] * n
        for _ in range(1, m):
            for j in range(1, n):
                dp[j] += dp[j - 1]
        return dp[-1]


def main():
    m, n = map(int, input().split())
    print(Solution().uniquePaths(m, n))


if __name__ == "__main__":
    main()

复杂度

  • 时间复杂度：O(mn)O(mn)。
  • 空间复杂度：O(n)O(n)。

总结

网格路径计数是二维 DP 的入门题。首行首列初始化为 1，转移方程 dp[i][j] = dp[i-1][j] + dp[i][j-1]，空间可优化到一维。