题目: 不同路径

来自智得网
跳转至： 导航、​ 搜索

方法一：动态规划

这种方法使用一个二维数组dp来记录到达每个格子的不同路径数。初始化dp数组的第一行和第一列为1，因为只能向右或向下移动。然后，从第二行第二列开始，对于每个格子，可以通过向右移动一步或向下移动一步到达。我们可以使用一个二维数组来保存从起点到当前位置的路径总数。具体来说，对于矩阵中的每个位置（i，j），路径总数等于上面的位置（i-1，j）和左边的位置（i，j-1）的路径总数之和。最后，返回dp数组的最后一个元素即为结果。

因此，我们可以使用以下递推公式来计算路径总数：dp[i][j] = dp[i-1][j] + dp[i][j-1]

其中dp是一个二维数组，dp[i][j]表示从起点到（i，j）位置的路径总数。 

#include <vector>

int uniquePaths(int m, int n) {
    std::vector<std::vector<int>> dp(m, std::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];
        }
    }
    
    return dp[m-1][n-1];
}

public int uniquePaths(int m, int n) {
    int[][] dp = new int[m][n];
    
    for (int i = 0; i < m; i++) {
        dp[i][0] = 1;
    }
    
    for (int j = 0; j < n; j++) {
        dp[0][j] = 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];
        }
    }
    
    return dp[m-1][n-1];
}

func uniquePaths(m int, n int) int {
    dp := make([][]int, m)
    
    for i := 0; i < m; i++ {
        dp[i] = make([]int, n)
        dp[i][0] = 1
    }
    
    for j := 0; j < n; j++ {
        dp[0][j] = 1
    }
    
    for i := 1; i < m; i++ {
        for j := 1; j < n; j++ {
            dp[i][j] = dp[i-1][j] + dp[i][j-1]
        }
    }
    
    return dp[m-1][n-1]
}

def uniquePaths(m, n):
    dp = [[1] * n] + [[1] + [0] * (n-1) for _ in range(m-1)]
    
    for i in range(1, m):
        for j in range(1, n):
            dp[i][j] = dp[i-1][j] + dp[i][j-1]
    
    return dp[m-1][n-1]

function uniquePaths(m, n) {
    const dp = new Array(m).fill(0).map(() => new Array(n).fill(0));
    
    for (let i = 0; i < m; i++) {
        dp[i][0] = 1;
    }
    
    for (let j = 0; j < n; j++) {
        dp[0][j] = 1;
    }
    
    for (let i = 1; i < m; i++) {
        for (let j = 1; j < n; j++) {
            dp[i][j] = dp[i-1][j] + dp[i][j-1];
        }
    }
    
    return dp[m-1][n-1];
}

方法二：组合数学

不同路径问题可以转化为组合数学问题。机器人需要向下移动m-1步，向右移动n-1步，总共需要移动m+n-2步。因此，问题可以转化为在这m+n-2步中选择m-1步或n-1步的组合数。可以使用组合数的公式来计算。

(m+n−2)!​/（(m−1)!(n−1)!） 

#include <vector>

int uniquePaths(int m, int n) {
    long long result = 1;
    
    for (int i = 1; i < n; i++) {
        result = result * (m + i - 1) / i;
    }
    
    return (int)result;
}

public int uniquePaths(int m, int n) {
    long result = 1;
    
    for (int i = 1; i < n; i++) {
        result = result * (m + i - 1) / i;
    }
    
    return (int)result;
}

func uniquePaths(m int, n int) int {
    result := int64(1)
    
    for i := 1; i < n; i++ {
        result = result * int64(m+i-1) / int64(i)
    }
    
    return int(result)
}

from math import comb

def uniquePaths(m, n):
    return comb(m + n - 2, n - 1)

function uniquePaths(m, n) {
    let result = 1;
    
    for (let i = 1; i < n; i++) {
        result = result * (m + i - 1) / i;
    }
    
    return Math.floor(result);
}

方法三：深度优先搜索

这种方法使用递归来计算不同路径数。从起点出发，每次可以选择向右移动或向下移动，直到到达终点。递归函数dfs用于计算从当前位置到达终点的路径数，通过递归调用向右和向下两个方向继续搜索。需要注意的是，为了避免重复计算，可以使用一个字典memo来保存已经计算过的路径数。 

int uniquePaths(int m, int n) {
    if (m == 1 || n == 1) {
        return 1;
    }
    
    return uniquePaths(m-1, n) + uniquePaths(m, n-1);
}

public int uniquePaths(int m, int n) {
    if (m == 1 || n == 1) {
        return 1;
    }
    
    return uniquePaths(m-1, n) + uniquePaths(m, n-1);
}

func uniquePaths(m int, n int) int {
    if m == 1 || n == 1 {
        return 1
    }
    
    return uniquePaths(m-1, n) + uniquePaths(m, n-1)
}

def uniquePaths(m, n):
    if m == 1 or n == 1:
        return 1
    
    return uniquePaths(m-1, n) + uniquePaths(m, n-1)

function uniquePaths(m, n) {
    if (m === 1 || n === 1) {
        return 1;
    }
    
    return uniquePaths(m-1, n) + uniquePaths(m, n-1);
}
取自“https://www.aigetting.com/index.php?title=题目:不同路径&oldid=2098”