小学生都能看懂的题解 | #不同路径的数目(一)#

不同路径的数目(一)

https://www.nowcoder.com/practice/166eaff8439d4cd898e3ba933fbc6358

好的,让我们用简单易懂的语言来解释这个问题的解决方案和代码。

问题描述

我们有一个 m 行 n 列的网格(想象成一个方块的棋盘),机器人从左上角出发,每次只能向下或向右移动。我们的目标是计算从起点(左上角)到终点(右下角)有多少条不同的路径。

解决方案

我们可以通过一个方法来找出所有可能的路径。这里我们使用一种叫做“动态规划”的方法,特别是只用一个一维数组来存储计算结果,这样可以节省空间。

代码解释

以下是我们的代码,并逐行解释每一部分:

public class RobotPaths {
    public int uniquePaths(int m, int n) {
        // 创建一个一维数组dp,长度为n
        int[] dp = new int[n];

  • int[] dp = new int[n];:我们创建了一个数组 dp,这个数组用来存储每一列到达那里的路径数量。这个数组的长度是 n(列的数量)。
        // 初始化第一行
        for (int j = 0; j < n; j++) {
            dp[j] = 1; // 只有一种方式到达第一行的每个格子
        }

  • for (int j = 0; j < n; j++):我们遍历每一列,给每个格子赋值为1。因为从左上角到达第一行的每个格子,只有一种方式(一直往右走)。
        // 计算路径数
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[j] += dp[j - 1]; // 当前格子的路径数 = dp[j-1] + dp[j]
            }
        }

  • 外层循环 for (int i = 1; i < m; i++):我们从第二行开始遍历,直到最后一行。
  • 内层循环 for (int j = 1; j < n; j++):我们从第二列开始遍历,直到最后一列。
  • dp[j] += dp[j - 1];:这句话的意思是当前格子的路径数量等于上面那个格子的路径数量(dp[j] 代表当前格子)加上左边那个格子的路径数量(dp[j - 1] 代表左边的格子)。这样,我们不断更新数组,最终可以得到到达右下角的所有路径数量。
        // 返回右下角的路径数量
        return dp[n - 1];
    }

  • return dp[n - 1];:最后,我们返回数组中最后一个元素的值,表示到达右下角的路径数量。

最后这里是完整的代码:

public class RobotPaths {
    public int uniquePaths(int m, int n) {
        // 创建一个一维数组dp,长度为n
        int[] dp = new int[n];

        // 初始化第一行
        for (int j = 0; j < n; j++) {
            dp[j] = 1; // 只有一种方式到达第一行的每个格子
        }

        // 计算路径数
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[j] += dp[j - 1]; // 当前格子的路径数 = dp[j-1] + dp[j]
            }
        }

        // 返回右下角的路径数量
        return dp[n - 1];
    }
}

希望这篇文章对你有帮助👍。

#题解#
小学生都能看懂的算法 文章被收录于专栏

主要面向小白的算法文章。以小学生都能看懂为目标而编写,顺便巩固下自己。

全部评论

相关推荐

哈哈哈哈哈哈哈哈哈哈这个世界太美好了
凉风落木楚山秋:毕业出路老师不管,你盖个章他好交差就完事了,等你盖完毕业了就不关他事情了
点赞 评论 收藏
分享
05-29 20:34
门头沟学院 C++
KarlAllen:得做好直接春招的准备。学历差的话,一是面试要求会比学历好的严格不少,二是就算面试通过了也会被排序。总之暑期和秋招对于学历差的就是及其不友好
无实习如何秋招上岸
点赞 评论 收藏
分享
07-05 16:23
门头沟学院 Java
mengnankk:我投了300,约了5 6个面试。感觉项目写的太多了。一个项目就写五六个亮点,不是把整个项目的功能描述下。其他的没啥,简历看起来有点长
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
07-07 18:05
哈哈哈哈哈感觉朋友找工作的已经疯掉了,直接上图
码农索隆:真老板娘:“我嘞个去,这不我当年的套路吗
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务