DAY38 ||62.不同路径 |63. 不同路径 II

62.不同路径

题目:62. 不同路径 - 力扣(LeetCode)

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

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

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

示例 1:

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

示例 2:

  • 输入:m = 2, n = 3
  • 输出:3

解释: 从左上角开始,总共有 3 条路径可以到达右下角。

  1. 向右 -> 向右 -> 向下
  2. 向右 -> 向下 -> 向右
  3. 向下 -> 向右 -> 向右

示例 3:

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

示例 4:

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

五部曲·思路

1.确定dp数组以及下标的含义

二维数组。。

dp[i][j]表示从(0,0)出发,到(i,j)有多少条不同的路径

2.确定递推公式

dp[i][j]=dp[i-1][j]+dp[i][j-1]。

因为只能从两个方向来。。。。

3.dp数组初始化

首先dp[i][0]一定都是1,因为从(0, 0)的位置到(i, 0)的路径只有一条(只能一直向右),那么dp[0][j]也同理。

4.确定遍历顺序

从左到右,从上到下遍历

5.举例dp数组

 代码

class Solution {
public:
    int uniquePaths(int m, int n) {
        vector<vector<int>>dp(m,vector<int>(n,0));//二维数组
        for(int i=0;i<m;i++)dp[i][0]=1;//起点出发一直向下的路径只有一条
        for(int j=0;j<n;j++)dp[0][j]=1;//起点出发一直向右的路径只有一条
        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];
        
    }
};

首先深度搜索(理解二叉树)是超时的,数论方法没看,。

 

 63. 不同路径 II

题目:63. 不同路径 II - 力扣(LeetCode)

给定一个 m x n 的整数数组 grid。一个机器人初始位于 左上角(即 grid[0][0])。机器人尝试移动到 右下角(即 grid[m - 1][n - 1])。机器人每次只能向下或者向右移动一步。

网格中的障碍物和空位置分别用 1 和 0 来表示。机器人的移动路径中不能包含 任何 有障碍物的方格。

返回机器人能够到达右下角的不同路径数量。

测试用例保证答案小于等于 2 * 109

示例 1:

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

示例 2:

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

五部曲

1.确定dp数组及其下标含义

在绕开了障碍物情况下,dp[i][j]表示从(0,0)出发,到(i,j)有多少条不同的路径

2.确定递推公式

dp[i][j] = dp[i - 1][j] + dp[i][j - 1]。但是!!(i, j)如果就是障碍的话应该就保持初始状态(初始状态为0)

3.dp数组初始化

和上题一样,最上边和最右边一栏的路径都只有一条。但是,如果遇到了障碍,那么以后的不同路径数都是0

4.遍历顺序

从左到右,从前到后

5.举例dp数组

如例一,那个路径数保持初始值0的就是障碍

代码

要注意区分网格数组(记录的空位置和障碍的情况)和dp数组(其含义是(i,j)的不同路径和)

 

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        int m = obstacleGrid.size();
        int n = obstacleGrid[0].size();

        if (obstacleGrid[m - 1][n - 1] == 1 || obstacleGrid[0][0] == 1) 
            return 0;//如果起点(obstacleGrid[0][0])或终点(obstacleGrid[m-1][n-1])有障碍物(1表示有障碍),则说明无法从起点到终点,所以直接返回 0。

        vector<vector<int>> dp(m, vector<int>(n, 0));
        //如果在某个位置有障碍物(obstacleGrid[i][0] == 1 或 obstacleGrid[0][j] == 1),则后续的位置就无法到达,因此后面的路径数保持为 0。
        for (int i = 0; i < m && obstacleGrid[i][0] == 0; i++) dp[i][0] = 1;
        for (int j = 0; j < n && obstacleGrid[0][j] == 0; j++) dp[0][j] = 1;

        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (obstacleGrid[i][j] == 1) continue;//跳过有障碍物的点
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];//对于没有障碍物的点 (i, j),它的路径数等于其上方位置 (i-1, j) 的路径数加上左边位置 (i, j-1) 的路径数
            }
        }
        return dp[m - 1][n - 1];//最终返回 dp[m-1][n-1],即到达终点位置的不同路径数。
    }
};

一刷跳过的两道题

343. 整数拆分 - 力扣(LeetCode)

96. 不同的二叉搜索树 - 力扣(LeetCode)

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

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

相关文章

李宏毅机器学习2022-HW7-BERT-Question Answering

文章目录 TaskBaselineMediumStrongBoss Code Link Task HW7的任务是通过BERT完成Question Answering。 数据预处理流程梳理 数据解压后包含3个json文件&#xff1a;hw7_train.json, hw7_dev.json, hw7_test.json。 DRCD: 台達閱讀理解資料集 Delta Reading Comprehension …

衡石分析平台系统分析人员手册-可视化报表仪表盘

仪表盘​ 仪表盘是数据分析最终展现形式&#xff0c;是数据分析的终极展现。 应用由一个或多个仪表盘展示&#xff0c;多个仪表盘之间有业务关联。 仪表盘编辑​ 图表列表​ 打开仪表盘后&#xff0c;就会看到该仪表盘中所有的图表。 调整图表布局​ 将鼠标移动到图表上拖动…

设计模式:类与类之间关系的表示方式(聚合,组合,依赖,继承,实现)

目录 聚合关系 组合关系 依赖关系 继承关系 实现关系 聚合关系 聚合是一种较弱的“拥有”关系&#xff0c;表示整体与部分的关系&#xff0c;但部分可以独立于整体存在。例如&#xff0c;部门和员工之间的关系&#xff0c;一个部门可以包含多个员工&#xff0c;但员工可以…

【大数据技术基础 | 实验四】HDFS实验:读写HDFS文件

文章目录 一、实验目的二、实验要求三、实验原理&#xff08;一&#xff09;Java Classpath&#xff08;二&#xff09;Eclipse Hadoop插件 四、实验环境五、实验内容和步骤&#xff08;一&#xff09;配置master服务器classpath&#xff08;二&#xff09;使用master服务器编写…

JOIN 表连接

1. 插入表测试数据 分别清空学生信息表 student、教师信息表 teacher、课程表 course、学生选课关联表 student_course 数据&#xff0c;并分别插入测试数据。 1.1 清空表数据 分别清空学生信息表 student、教师信息表 teacher、课程表 course、学生选课关联表 student_cours…

第8篇:网络安全基础

目录 引言 8.1 网络安全的基本概念 8.2 网络威胁与攻击类型 8.3 密码学的基本思想与加密算法 8.4 消息认证与数字签名 8.5 网络安全技术与协议 8.6 总结 第8篇&#xff1a;网络安全基础 引言 在现代信息社会中&#xff0c;计算机网络无处不在&#xff0c;从互联网到局…

Atlas800昇腾服务器(型号:3000)—驱动与固件安装(一)

服务器配置如下&#xff1a; CPU/NPU&#xff1a;鲲鹏 CPU&#xff08;ARM64&#xff09;A300I pro推理卡 系统&#xff1a;Kylin V10 SP1【下载链接】【安装链接】 驱动与固件版本版本&#xff1a; Ascend-hdk-310p-npu-driver_23.0.1_linux-aarch64.run【下载链接】 Ascend-…

0x3D service

0x3D service 1. 概念2. Request message 数据格式3. Respone message 数据格式3.1 正响应格式3.2 negative respone codes(NRC)4. 示例4.1 正响应示例:4.2 NRC 示例1. 概念 UDS(统一诊断服务)中的0x3D服务,即Write Memory By Address(按地址写内存)服务,允许客户端向服…

艺术家杨烨炘厦门开展,49只“鞋底倒计时”引轰动

艺术家杨烨炘 9&#xff0c;8&#xff0c;7&#xff0c;6&#xff0c;5&#xff0c;4&#xff0c;3&#xff0c;2&#xff0c;1&#xff0c;0………近日&#xff0c;一件名为《走向倒计时》的艺术作品在厦门引发讨论。艺术家杨烨炘邀请49位台湾同胞&#xff0c;将他们的鞋底拼成…

51单片机快速入门之 LCD1602 液晶显示屏2024/10/19

51单片机快速入门之 LCD1602 液晶显示屏 Proteus 电路图 : 74HC595 拓展电路可以不用,给 p0-p17 添加上拉电阻也可以!,我这里是方便读取和节省电阻线路 (因为之前不知道 在没有明确循环的情况下&#xff0c;Keil编译器可能会在main()中自动添加类似以下的汇编代码&#xff1a…

基于SpringBoot中药材进存销管理系统【附源码】

基于SpringBoot中药材进存销管理系统 效果如下&#xff1a; 系统注册界面 管理员主界面 员工界面 供应商界面 中药材类型界面 中药材界面 员工主界面 研究背景 随着中医药产业的快速发展&#xff0c;传统的管理方式已难以满足现代化、规模化的药材管理需求。中药材种类繁多&…

Vulnhub打靶-matrix-breakout-2-morpheus

基本信息 靶机下载&#xff1a;https://pan.baidu.com/s/1kz6ei5hNomFK44p1QT0xzQ?pwdy5qh 提取码: y5qh 攻击机器&#xff1a;192.168.20.128&#xff08;Windows操作系统&#xff09; 靶机&#xff1a;192.168.20.0/24 目标&#xff1a;获取2个flagroot权限 具体流程 …

基于FreeRTOS的LWIP移植

目录 前言一、移植准备工作二、以太网固件库与驱动2.1 固件库文件添加2.2 库文件修改2.3 添加网卡驱动 三、LWIP 数据包和网络接口管理3.1 添加LWIP源文件3.2 Lwip文件修改3.2.1 修改cc.h3.2.2 修改lwipopts.h3.2.3 修改icmp.c3.2.4 修改sys_arch.h和sys_arch.c3.2.5 修改ether…

【NOIP提高组】一元三次方程求解

【NOIP提高组】一元三次方程求解 &#x1f490;The Begin&#x1f490;点点关注&#xff0c;收藏不迷路&#x1f490; 有形如&#xff1a;ax3bx2cxd0 这样的一个一元三次方程。给出该方程中各项的系数(a&#xff0c;b&#xff0c;c&#xff0c;d均为实数)&#xff0c;并约定该方…

图像梯度-Sobel算子、scharrx算子和lapkacian算子

文章目录 一、认识什么是图像梯度和Sobel算子二、Sobel算子的具体使用三、scharrx算子与lapkacian(拉普拉斯)算子 一、认识什么是图像梯度和Sobel算子 图像的梯度是指图像亮度变化的空间导数&#xff0c;它描述了图像在不同方向上的强度变化。在图像处理和计算机视觉中&#x…

Unity使用Git及GitHub进行项目管理

git: 工作区,暂存区(存放临时要存放的内容),代码仓库区1.初始化 git init 此时展开隐藏项目,会出现.git文件夹 2.减小项目体积 touch .gitignore命令 创建.gitignore文件夹 gitignore文件夹的内容 gitignore中添加一下内容 # This .gitignore file should be place…

2025秋招八股文--网络原理篇

前言 1.本系列面试八股文的题目及答案均来自于网络平台的内容整理&#xff0c;对其进行了归类整理&#xff0c;在格式和内容上或许会存在一定错误&#xff0c;大家自行理解。内容涵盖部分若有侵权部分&#xff0c;请后台联系&#xff0c;及时删除。 2.本系列发布内容分为12篇…

《Linux从小白到高手》综合应用篇:深入理解Linux常用关键内核参数及其调优

1. 题记 有关Linux关键内核参数的调整&#xff0c;我前面的调优文章其实就有涉及到&#xff0c;只是比较零散&#xff0c;本篇集中深入介绍Linux常用关键内核参数及其调优&#xff0c;Linux调优80%以上都涉及到内核的这些参数的调整。 2. 文件系统相关参数 fs.file-max 参数…

VMware虚拟机的下载安装与使用

目录 一、下载VMware虚拟机 步骤1---找到需要的虚拟机下载位置 步骤2---找到下载的安装包安装程序 二、删除干净VMware虚拟机 步骤1--进去服务里面关闭虚拟机服务 步骤2---控制面板里面删除 步骤3---注册表删除HKEY_CURRENT_USER\Software\VMware, Inc. 步骤4---安装在…

政安晨【零基础玩转各类开源AI项目】基于本地Ubuntu (Linux ) 系统应用Gradio-Lite:无服务器 Gradio 完全在浏览器中运行

目录 简介 什么是gradio/lite&#xff1f; 入门 1.导入 JS 和 CSS 2. 创建标签 3. 在标签内编写你的 Gradio 应用程序 更多示例&#xff1a;添加其他文件和要求 多个文件 其他要求 SharedWorker 模式 代码和演示playground 1.无服务器部署 2.低延迟 3. 隐私和安全…