leetcode 不同路径

62. 不同路径

问题描述

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

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

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

示例 1:

在这里插入图片描述

输入: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
  • 题目数据保证答案小于等于 2 * 109

解题思路与代码实现

class Solution {
    // 解法一:动态规划
    public int uniquePaths(int m, int n) {
        // dp数组,dp[i][j]表示到达(i,j)的路径数量
        int[][] dp = new int[m][n];
        // 数组初始化,左上边界初始化为1
        for(int i=0;i<m;i++){
            dp[i][0]=1;
        }
        for(int j=0;j<n;j++){
            dp[0][j]=1;
        }
        // dp求解
        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];

    }
}
class Solution {
    // 解法二:转为求组合数
    public int uniquePaths(int m, int n) {
        // 总共需要走m+n-2步,其中向右n-1,向下m-1,即为求组合数问题
        int y  = m+n-2; // 总步数
        int x = Math.min(m-1,n-1);    // 组合数性质
        return calculateCombination(y,x);
    }

    // 求组合数
    public  int calculateCombination(int y, int x) {
        x = Math.min(x, y-x);
        long result = 1;
        // 为防止溢出,转化成:(y-x+1)*...*y/[1*..*x]
        for (int i = 1; i <= x; i++) {
            result *= y - x + i;
            result /= i;
        }
        return (int)result;
    }

}

踩坑点

63. 不同路径 II

问题描述

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

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

现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径?

网格中的障碍物和空位置分别用 10 来表示。

示例 1:

在这里插入图片描述

输入:obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
输出:2
解释:3x3 网格的正中间有一个障碍物。
从左上角到右下角一共有 2 条不同的路径:
1. 向右 -> 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右 -> 向右

示例 2:

在这里插入图片描述

输入:obstacleGrid = [[0,1],[0,0]]
输出:1

提示:

  • m == obstacleGrid.length
  • n == obstacleGrid[i].length
  • 1 <= m, n <= 100
  • obstacleGrid[i][j]01

解题思路与代码实现

class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m=obstacleGrid.length, n = obstacleGrid[0].length;
        // 如果起点或者终点有障碍物,无法抵达,返回0
        if(obstacleGrid[0][0] == 1|| obstacleGrid[m-1][n-1]==1){
            return 0;
        }
        // dp数组,dp[i][j]表示到达(i,j)的路径数量
        int[][] dp = new int[m][n];
        // 数组初始化,左上边界初始化为1
        for(int i=0;i<m;i++){
            // 如果有障碍物,则停止初始化
            if(obstacleGrid[i][0]==1){
                break;
            }
            dp[i][0] = 1;
        }
        for(int j=0;j<n;j++){
            // 如果有障碍物,则停止初始化
            if(obstacleGrid[0][j]==1){
                break;
            }
            dp[0][j]=1;
        }
        // dp求解
        for(int i=1;i<m;i++){
            for(int j=1;j<n;j++){
                // 当前位置有障碍物
                if(obstacleGrid[i][j]==1){
                    dp[i][j]=0;
                    continue;
                }
                // 递推方程:dp[i][j]的组合数等于左侧dp[i][j-1]和顶部dp[i-1][j]的和
                dp[i][j] = dp[i-1][j] + dp[i][j-1];
            }
        }
        return dp[m-1][n-1];
    }
}

踩坑点

对于障碍物如何处理

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/505685.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

python_2

文章目录 题目一运行结果 题目二运行结果 题目一 代码如下&#xff1a; def merge():ls_0 input("输入一个列表(空格隔开)&#xff1a;").split()ls_1 []for i in ls_0:ls_1.append(i)ls_1.sort()if ls_0 ls_1:print("这是一个有序列表")else:print(&qu…

国内首个BEV感知全栈系列学习教程:课程总结

目录 前言零. 简述一、BEV感知算法介绍二、BEV感知算法基础模块讲解三、LiDAR和Camera融合的BEV感知算法四、基于环视Camera的BEV感知算法五、BEV感知算法实战总结 前言 自动驾驶之心推出的《国内首个BVE感知全栈系列学习教程》&#xff0c;链接。记录下个人学习笔记&#xff0…

系统慢查询的思考

系统慢查询的思考 在一个系统中发现慢查询的功能或很卡的现象。你是怎么思考的&#xff1f;从哪几个方面去思考&#xff1f;会用什么工具&#xff1f; 一个系统使用了几年后都可能会出现这样的问题。原因可能有以下几点。 数据量的增加。系统中平时的使用中数据量是有一个累…

cdr弧形线条怎么画 cdr弧形线条怎么复制 CoreIDRAW官版 CoreIDRAW2024 平面设计软件

弧形线条可以增加设计的美感和独特性&#xff0c;使其看起来更加优雅和精致&#xff0c;并且弧形线条可以使设计更加流畅&#xff0c;减少直角和生硬的转折&#xff0c;使其看起来更加自然。那在cdr软件中怎么绘制弧形线条呢&#xff1f;下面由我带大家一起来了解cdr弧形线条怎…

c++编程(1)——重载函数、引用

欢迎来到博主的专栏——c编程 博主ID&#xff1a; 代码小豪 文章目录 前言重载函数函数重载的规则函数重载的原理引用引用变量的权限问题 前言 c语言对于编写大型项目有所缺陷&#xff0c;比如最常出现的标识符不能重复的问题&#xff08;软件的代码量通常是数以万计的&#…

机器语言编写helloworld

kvmtool下载编译 git clone https://github.com/kvmtool/kvmtool.git 下载后进入到目录执行make即可。 补码 计算机怎么表示负数&#xff1f;以四位有符号数为例&#xff0c;使用高位作为符号位&#xff0c;最高位为0表示正数&#xff0c;为1表示负数&#xff0c;其余三位用…

基于SSM远程同步课堂系统

基于SSM远程同步课堂系统的设计与实现 摘要 在这样一个网络数据大爆炸的时代&#xff0c;人们获取知识、获取信息的通道非常的多元化&#xff0c;通过网络来实现数据信息的获取成为了现在非常常见的一种方式&#xff0c;而通过网络进行教学&#xff0c;在网络上进行远程的课堂…

【软考】数据流图的设计原则

目录 1. 数据守恒原则2. 守恒加工原则3. 外部实体与外部实体之间不存在数据流4. 外部实体与外部存储之间不存在数据流5. 数据存储与数据存储之间不存在数据流6. 父图与子图的平衡原则7. 数据流与加工有关&#xff0c;且必须经过加工8.例题8.1 例题1 1. 数据守恒原则 1.输入与输…

嵌入式linux学习之opencv交叉编译

1.下载opencv源码 OpenCV官方源码下载链接为https://opencv.org/releases/&#xff0c;选择3.4.16版本下载。放在ubuntu系统~/opencv文件夹中&#xff0c;解压缩&#xff0c;opencv文件夹中新建build和install文件夹用于存放编译文件和安装文件&#xff1a; 2. 安装编译工具…

ES的RestClient相关操作

ES的RestClient相关操作 Elasticsearch使用Java操作。 本文仅介绍CURD索引库和文档&#xff01;&#xff01;&#xff01; Elasticsearch基础&#xff1a;https://blog.csdn.net/weixin_46533577/article/details/137207222 Elasticsearch Clients官网&#xff1a;https://ww…

MD5 计算 (下一代加密辅助类, Win32, C++)

CCNGHelper.h #pragma once #include <string> #include <tchar.h> #include <windows.h> #include <bcrypt.h>#ifdef _UNICODE using _tstring std::wstring; #else using _tstring std::string; #endif// 下一代加密辅助类 // 客户端: Windows Vi…

Vue2(十二):Vuex环境搭建、Vuex工作原理、Vuex开发者工具、几个配置项、多组件共享数据、Vuex模块化

一、Vuex 1.概念 专门在Vue中实现集中式状态&#xff08;数据&#xff09;管理的一个Vue插件&#xff08;use引入&#xff09;&#xff0c;对vue应用中多个组件的共享状态进行集中式的管理&#xff08;读&#xff0f;写&#xff09;&#xff0c;也是一种组件间通信的方式&…

阿里云优惠券领取方法大公开,省钱不再是难事

阿里云作为国内领先的云计算服务提供商&#xff0c;为广大用户提供了丰富的云产品和解决方案。为了吸引用户上云&#xff0c;阿里云经常推出各种优惠活动&#xff0c;其中最受用户欢迎的就是阿里云优惠券。那么&#xff0c;阿里云优惠券究竟是什么呢&#xff1f;我们又该如何领…

代码随想录第25天|216.组合总和III 17.电话号码的字母组合

216.组合总和III 216. 组合总和 III - 力扣&#xff08;LeetCode&#xff09; 代码随想录 (programmercarl.com) 和组合问题有啥区别&#xff1f;回溯算法如何剪枝&#xff1f;| LeetCode&#xff1a;216.组合总和III_哔哩哔哩_bilibili 找出所有相加之和为 n 的 k 个数的组…

基于自动编码器的预训练模型方法模型预训练方法RetroMAE和RetroMAE-2

文章目录 RetroMAERetroMAE详情编码解码增强解码 RetroMAE-2RetroMAE-2详情编码[CLS]解码OT解码和训练目标向量表征 总结参考资料 RetroMAE RetroMAE 出自论文《RetroMAE: Pre-Training Retrieval-oriented Language Models Via Masked Auto-Encoder》&#xff0c;是一种针对于…

「MySQL」索引事务

&#x1f387;个人主页&#xff1a;Ice_Sugar_7 &#x1f387;所属专栏&#xff1a;数据库 &#x1f387;欢迎点赞收藏加关注哦&#xff01; 索引&事务 &#x1f349;索引&#x1f34c;特点&#x1f34c;通过 SQL 操作索引&#x1f34c;底层数据结构 &#x1f349;事务&…

网络编程的学习1

网络编程 在网络通信协议下&#xff0c;不同计算机上运行的程序&#xff0c;进行数据传输。 三要素 ip&#xff1a;设备在网络中的地址&#xff0c;是唯一的标识。 ipv4:采取32位地址长度&#xff0c;分成4组。 ipv6&#xff1a;采用128位地址长度&#xff0c;分成8组。 …

安卓SharedPreferences使用

目录 一、简介二、使用2.1 getSharedPreferences2.2 增加数据2.3 读取数据2.4 删除数据2.5 修改数据2.6 清除数据2.7 提交数据 一、简介 SharedPreferences是Android平台上一个轻量级的存储类&#xff0c;主要是保存一些常用的配置比如窗口状态&#xff0c;一般在Activity、重…

12.Python文件读写

文件是数据的载体&#xff0c;程序可以从文件中读取数据&#xff0c;也可以将数据写 入文件中&#xff0c;本章重点介绍如何在Python中进行文件读写。 1 打开文件 我们在使用文件之前要先将文件打开&#xff0c;这通过open&#xff08;&#xff09;函数实现。 open&#xff0…

JJJ:linux系统中第一个进程

以linux4.19内核linux系统中第一个进程。 执行shell指令 ps -ef 结果如下&#xff1a; xxxxxx-virtual-machine:~$ ps -ef UID PID PPID C STIME TTY TIME CMD root 1 0 0 20:55 ? 00:00:02 /sbin/init splash root …