题解 | 不同路径的数目(一)

1、解题思路

1. 动态规划：定义 dp[i][j] 为从起点 (0, 0) 到 (i, j) 的不同路径数。递推关系： dp[i][j] = dp[i-1][j] + dp[i][j-1]。初始条件： dp[0][j] = 1（表示只能向右走）。dp[i][0] = 1（表示只能向下走）。
2. 空间优化：使用滚动数组优化空间，将空间复杂度从 O(m × n) 降为 O(n) 或 O(m)。
3. 数学方法（进阶）：使用组合数学公式，路径数为 C(m+n-2, m-1) 或 C(m+n-2, n-1)。计算组合数时，可以利用乘法公式避免大数计算。

2、代码实现

C++

#include <vector>
class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param m int整型
     * @param n int整型
     * @return int整型
     */
    int uniquePaths(int m, int n) {
        // write code here
        vector<vector<int>> dp(m, vector<int>(n, 1));   // 空间 O(m × n)
        for (int i = 1; i < m; ++i) { // 时间 O(m × n)
            for (int j = 1; j < n; ++j) {
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }
        return dp[m - 1][n - 1];
    }
};

Java

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param m int整型 
     * @param n int整型 
     * @return int整型
     */
    public int uniquePaths (int m, int n) {
        // write code here
        int[][] dp = new int[m][n]; // 空间 O(m × n)
        for (int i = 0; i < m; ++i) { // 时间 O(m × n)
            for (int j = 0; j < n; ++j) {
                if (i == 0 || j == 0) {
                    dp[i][j] = 1;
                } else {
                    dp[i][j] = dp[i-1][j] + dp[i][j-1];
                }
            }
        }
        return dp[m-1][n-1];
    }
}

Python

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param m int整型 
# @param n int整型 
# @return int整型
#
class Solution:
    def uniquePaths(self , m: int, n: int) -> int:
        # write code here
        dp = [[1] * n for _ in range(m)] # 空间 O(m × n)
        for i in range(1, m): # 时间 O(m × n)
            for j in range(1, n):
                dp[i][j] = dp[i-1][j] + dp[i][j-1]
        return dp[m-1][n-1]

3、复杂度分析

• 时间复杂度：O(m × n)，其中 m 和 n 分别是地图的行数和列数。
• 空间复杂度：O(m × n)，用于存储 dp 表格。