【Leetcode】62. 不同路径

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

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

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

示例1:

【Leetcode】62. 不同路径
输入:m = 3, n = 7
输出:28

示例2:

输入:m = 3, n = 2
输出:3
解释:
从左上角开始,总共有 3 条路径可以到达右下角。
1. 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右
3. 向下 -> 向右 -> 向下

示例3:

输入:m = 7, n = 3
输出:28

示例 4:

输入:m = 3, n = 3
输出:6

提示:

  • 1 <= m, n <="100</code"><!--=-->
  • &#x9898;&#x76EE;&#x6570;&#x636E;&#x4FDD;&#x8BC1;&#x7B54;&#x6848;&#x5C0F;&#x4E8E;&#x7B49;&#x4E8E; 2 * 109

题解

思路:

  • 动态规划
  • 终点位置可以从上面过来或者从左边过来,所以计算从上面过来的路径数+从左边过来的路径数就可以得到总的路径数。其中,特殊判断第一行和第一列,因为这两个位置只有一种走的方案,即第一行只能从左边过来,第一列只能从上面过来。

code:

class Solution {
public:
    int uniquePaths(int m, int n) {
        int f[m + 10][n + 10];

        for (int i = 0; i < m; i ++){
            for (int j = 0; j < n; j ++){
                if (i == 0 || j == 0){
                    f[i][j] = 1;
                    continue;
                }
                f[i][j] = f[i - 1][j] + f[i][j - 1];
            }
        }

        return f[m - 1][n - 1];
    }
};

Original: https://www.cnblogs.com/Timesi/p/16691126.html
Author: 顾北清
Title: 【Leetcode】62. 不同路径

原创文章受到原创版权保护。转载请注明出处:https://www.johngo689.com/578191/

转载文章受原作者版权保护。转载请注明原作者出处!

(0)

大家都在看

  • Isilon 的OneFs常见操作命令(一)

    1背景知识: Isilon的oneFS是基于Free BSD的,FreeBSD 是一种类UNIX操作系统,因此有些类似Linux操作系统的常见命令可以直接使用,但有些又略微差别,需…

    Linux 2023年6月6日
    0107
  • 在 Windows 搭建 SVN 服务

    以下内容为本人的学习笔记,如需要转载,请声明原文链接微信公众号「englyf」 https://mp.weixin.qq.com/s/JIKNVuH5FIwEQMnYGxmRiQ …

    Linux 2023年6月6日
    0104
  • Linux 显示硬盘使用情况

    注入产生的原理: 数据库设置为GBK编码: 宽字节注入源于程序员设置MySQL连接时错误配置为:set character_set_client=gbk,这样配置会引发编码转换从而…

    Linux 2022年8月24日
    0251
  • Linux同时输出到管道和标准输出

    注入产生的原理: 数据库设置为GBK编码: 宽字节注入源于程序员设置MySQL连接时错误配置为:set character_set_client=gbk,这样配置会引发编码转换从而…

    Linux 2022年9月10日
    0213
  • python虚拟环境介绍与安装(不借助anaconda)

    1 虚拟环境介绍 (1) 虚拟环境能对不同的状况进行环境隔离,程序A的环境变动不会影响程序B的开发 (2)比较便携,因为虚拟环境中都有各自的python包,U盘复制环境,省去其他人…

    Linux 2023年6月7日
    076
  • Linux服务文件位置

    注入产生的原理: 数据库设置为GBK编码: 宽字节注入源于程序员设置MySQL连接时错误配置为:set character_set_client=gbk,这样配置会引发编码转换从而…

    Linux 2022年8月24日
    0232
  • SQLI-LABS(Less-6)

    Less-6(GET-Double injection-Double Quotes-String) 打开 Less-6页面,可以看到页面中间有一句 Please input the…

    Linux 2023年6月6日
    072
  • redis应用-sortedset实现排行榜(转载)

    package site.zy9.redisApp.test; import java.util.HashMap; import java.util.List; import ja…

    Linux 2023年5月28日
    083
  • linux的system () 函数详解

    注入产生的原理: 数据库设置为GBK编码: 宽字节注入源于程序员设置MySQL连接时错误配置为:set character_set_client=gbk,这样配置会引发编码转换从而…

    Linux 2022年8月24日
    0242
  • 系统复位到操作系统启动的简要流程图

    注入产生的原理: 数据库设置为GBK编码: 宽字节注入源于程序员设置MySQL连接时错误配置为:set character_set_client=gbk,这样配置会引发编码转换从而…

    Linux 2022年11月7日
    0173
  • linux与windows的批处理应用

    注入产生的原理: 数据库设置为GBK编码: 宽字节注入源于程序员设置MySQL连接时错误配置为:set character_set_client=gbk,这样配置会引发编码转换从而…

    Linux 2022年11月8日
    0180
  • phpcms v9编辑器上传图片是否添加水印

    第一步:给图片上传对话框里面添加是否添加水印的多选框,找到: satics/js/ckeditor/ckeditor.js 第17554行 (需要格式化,我用的NetBeans)修…

    Linux 2023年6月13日
    065
  • linux下禁止root用户登录,修改远程ssh登录端口号

    注入产生的原理: 数据库设置为GBK编码: 宽字节注入源于程序员设置MySQL连接时错误配置为:set character_set_client=gbk,这样配置会引发编码转换从而…

    Linux 2022年8月20日
    0262
  • 剑指offer计划25(模拟中等)—java

    1.1、题目1 剑指 Offer 29. 顺时针打印矩阵 1.2、解法 常规开头,先判断特殊情况,然后创建四个变量存放矩阵四边的长度限制。创建res数组存放结果。循坏开始,遍历完一…

    Linux 2023年6月11日
    075
  • Linux 命令多到记不住?这个开源项目帮你一网打尽!

    注入产生的原理: 数据库设置为GBK编码: 宽字节注入源于程序员设置MySQL连接时错误配置为:set character_set_client=gbk,这样配置会引发编码转换从而…

    Linux 2022年8月26日
    0270
  • 真正在大厂干了几年,我学会了反内卷[转]

    内卷这个概念的内涵很丰富,与我们的生活息息相关。为了普及和传播知识,我参考了相关的信息,把我个人的粗浅理解奉献给朋友们。 什么是内卷? 内卷 involution,与之对应的是 e…

    Linux 2023年6月8日
    093
亲爱的 Coder【最近整理,可免费获取】👉 最新必读书单  | 👏 面试题下载  | 🌎 免费的AI知识星球