一、题目描述

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

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

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

image-20211218102058227

二、题目解析

三、参考代码

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++ 代码

3、Python 代码

四、动画理解(没有声音)

隐藏内容
  • 普通用户购买价格:不可购买
  • 会员用户购买价格:999积分
  • 永久会员用户购买价格:免费推荐

发表评论

邮箱地址不会被公开。 必填项已用*标注