LeetCode 62、不同路径

一、题目描述

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。

问总共有多少条不同的路径？

二、题目解析

三、参考代码

1、Java 代码

// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者：程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 不同路径（ LeetCode 62 ）：https://leetcode-cn.com/problems/unique-paths/
class Solution {
    public int uniquePaths(int m, int n) {
        // 设置二维数组 dp 用来储存到达每个位置时不同路径的数量
        // dp[0][0] 表示从第 0 行第 0 列到达第 0 行第 0 列时不同路径的数量
        // dp[0][i] 表示从第 0 行第 0 列到达第 0 行第 i 列时不同路径的数量
        // dp[j][0] 表示从第 0 行第 0 列到达第 j 行第 0 列时不同路径的数量
        // dp[i][j] 表示从第 0 行第 0 列到达第 i 行第 j 列时不同路径的数量
        int[][] dp = new int[m][n];

        // 初始化 dp[0][0]，
        // dp[0][0] 表示从第 0 行第 0 列到达第 0 行第 0 列时不同路径的数量
        // 仅此一条，别无分路
        dp[0][0] = 1;

       

        // i 从 1 遍历到 m - 1 
        // 获取从第 0 行第 0 列到达第 j 行第 0 列时不同路径的数量
        // 由于每次只能向下或者向右移动一步，此时只能向下移动一步
        // 所以，只能一直向下走，只有这一条路径
        for(int i = 1; i < m ; i++){
            // 仅此一条，别无分路
            dp[i][0] = 1;
        }

        // j 从 1 遍历到 n - 1 
        // 获取从第 0 行第 0 列到达第 0 行第 i 列时不同路径的数量
        // 由于每次只能向下或者向右移动一步，此时只能向右移动一步
        // 所以，只能一直向右走，只有这一条路径
        for(int j = 1; j < n ; j++){
            // 仅此一条，别无分路
            dp[0][j] = 1;
        }

        // 接下来从第 1 行到第 m - 1 行
        // 从第 1 列到 n - 1 列
        // 填充二维数组 dp 里面的值
        // dp[i][j] 表示从第 0 行第 0 列到达第 i 行第 j 列时不同路径的数量
        for (int i = 1; i < m; i++) {

            for (int j = 1; j < n; j++) {
                // 由于每次只能向下或者向右移动一步
                // 位置 (i,j) 的不同路径的数量是由
                // 1、上边位置 dp[ i - 1 ][j] 的不同路径的数量
                // 2、左边位置 dp[i][ j - 1 ] 的不同路径的数量
                // 两者之和获取到的
                dp[i][j] = dp[ i - 1 ][j] + dp[i][ j - 1 ];
            }
        }

        // dp[ m - 1][ n - 1 ] 表示从第 0 行第 0 列到达第 m - 1 行第 n - 1 列时不同路径的数量
        // 即到达终点的数量
        // 返回这个结果即可
        return dp[ m - 1 ][ n - 1 ];
    }
}

**2、**C++ 代码

class Solution {
public:
    int uniquePaths(int m, int n) {
        // 设置二维数组 dp 用来储存到达每个位置时不同路径的数量
        // dp[0][0] 表示从第 0 行第 0 列到达第 0 行第 0 列时不同路径的数量
        // dp[0][i] 表示从第 0 行第 0 列到达第 0 行第 i 列时不同路径的数量
        // dp[j][0] 表示从第 0 行第 0 列到达第 j 行第 0 列时不同路径的数量
        // dp[i][j] 表示从第 0 行第 0 列到达第 i 行第 j 列时不同路径的数量
        auto dp = vector < vector < int>> ( m ,vector<int> ( n));

        // 初始化 dp[0][0]，
        // dp[0][0] 表示从第 0 行第 0 列到达第 0 行第 0 列时不同路径的数量
        // 仅此一条，别无分路
        dp[0][0] = 1;

        // i 从 1 遍历到 m - 1 
        // 获取从第 0 行第 0 列到达第 j 行第 0 列时不同路径的数量
        // 由于每次只能向下或者向右移动一步，此时只能向下移动一步
        // 所以，只能一直向下走，只有这一条路径
        for(int i = 1; i < m ; i++){
            // 仅此一条，别无分路
            dp[i][0] = 1;
        }

        // j 从 1 遍历到 n - 1 
        // 获取从第 0 行第 0 列到达第 0 行第 i 列时不同路径的数量
        // 由于每次只能向下或者向右移动一步，此时只能向右移动一步
        // 所以，只能一直向右走，只有这一条路径
        for(int j = 1; j < n ; j++){
            // 仅此一条，别无分路
            dp[0][j] = 1;
        }

        // 接下来从第 1 行到第 m - 1 行
        // 从第 1 列到 n - 1 列
        // 填充二维数组 dp 里面的值
        // dp[i][j] 表示从第 0 行第 0 列到达第 i 行第 j 列时不同路径的数量
        for (int i = 1; i < m; i++) {

            for (int j = 1; j < n; j++) {
                // 由于每次只能向下或者向右移动一步
                // 位置 (i,j) 的不同路径的数量是由
                // 1、上边位置 dp[ i - 1 ][j] 的不同路径的数量
                // 2、左边位置 dp[i][ j - 1 ] 的不同路径的数量
                // 两者之和获取到的
                dp[i][j] = dp[ i - 1 ][j] + dp[i][ j - 1 ];
            }
        }

        // dp[ m - 1][ n - 1 ] 表示从第 0 行第 0 列到达第 m - 1 行第 n - 1 列时不同路径的数量
        // 即到达终点的数量
        // 返回这个结果即可
        return dp[ m - 1 ][ n - 1 ];
    }
};

3、Python 代码

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        # 设置二维数组 dp 用来储存到达每个位置时不同路径的数量
        # dp[0][0] 表示从第 0 行第 0 列到达第 0 行第 0 列时不同路径的数量
        # dp[0][i] 表示从第 0 行第 0 列到达第 0 行第 i 列时不同路径的数量
        # dp[j][0] 表示从第 0 行第 0 列到达第 j 行第 0 列时不同路径的数量
        # dp[i][j] 表示从第 0 行第 0 列到达第 i 行第 j 列时不同路径的数量
        dp = [[0] * n for _ in range(m)]

        # 初始化 dp[0][0]，
        # dp[0][0] 表示从第 0 行第 0 列到达第 0 行第 0 列时不同路径的数量
        # 仅此一条，别无分路
        dp[0][0] = 1

        # i 从 1 遍历到 m - 1 
        # 获取从第 0 行第 0 列到达第 j 行第 0 列时不同路径的数量
        # 由于每次只能向下或者向右移动一步，此时只能向下移动一步
        # 所以，只能一直向下走，只有这一条路径
        for i in range( 1 , m ):
            # 仅此一条，别无分路
            dp[i][0] = 1
        

        # j 从 1 遍历到 n - 1 
        # 获取从第 0 行第 0 列到达第 0 行第 i 列时不同路径的数量
        # 由于每次只能向下或者向右移动一步，此时只能向右移动一步
        # 所以，只能一直向右走，只有这一条路径
        for j in range( 1 , n ):
            # 仅此一条，别无分路
            dp[0][j] = 1

        # 接下来从第 1 行到第 m - 1 行
        # 从第 1 列到 n - 1 列
        # 填充二维数组 dp 里面的值
        # dp[i][j] 表示从第 0 行第 0 列到达第 i 行第 j 列时不同路径的数量
        for i in range( 1 , m ):

            for j in range( 1 , n ):
                # 由于每次只能向下或者向右移动一步
                # 位置 (i,j) 的不同路径的数量是由
                # 1、上边位置 dp[ i - 1 ][j] 的不同路径的数量
                # 2、左边位置 dp[i][ j - 1 ] 的不同路径的数量
                # 两者之和获取到的
                dp[i][j] = dp[ i - 1 ][j] + dp[i][ j - 1 ]
     

        # dp[ m - 1][ n - 1 ] 表示从第 0 行第 0 列到达第 m - 1 行第 n - 1 列时不同路径的数量
        # 即到达终点的数量
        # 返回这个结果即可
        return dp[ m - 1 ][ n - 1 ]