leetcode 63. 不同路径 II

2023.8.9

        这题是不同路径I的升级版,在路径上增加了障碍物,有障碍物的地方无法通过。

        我的思路依然还是使用动态规划,dp[i][j]的含义依然是到(i,j)这个位置的路径个数。只需要在dp数组中将有障碍物的地方赋为0。大致步骤如下:

  • 先进行极端情况判断:当起始位置为障碍物时,无法到达终点,直接返回0。
  • 然后对第一行和第一列进行初始化,有障碍物的地方赋为0,无障碍物的地方赋为其左方或者上方的值。
  • 用两个for循环递推赋值,递推公式和不同路径I 一样,当前位置的路径个数 = 上方位置路径个数 + 左方位置的路径个数。  

        代码如下:

class Solution {
public:int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {if(obstacleGrid[0][0] == 1) return 0; //起点就是障碍物int m = obstacleGrid.size();int n = obstacleGrid[0].size();vector<vector<int>> dp(m , vector<int>(n));dp[0][0] = 1;//第一行初始化赋值for(int i=1; i<n; i++){//有障碍物if(obstacleGrid[0][i] == 1) dp[0][i] = 0;//无障碍物else dp[0][i] = dp[0][i-1];}//第一列初始化赋值for(int i=1; i<m; i++){if(obstacleGrid[i][0] == 1) dp[i][0] = 0;else dp[i][0] = dp[i-1][0];}//遍历递推赋值for(int i=1; i<m; i++){for(int j=1; j<n; j++){if(obstacleGrid[i][j] == 1) dp[i][j] = 0; //有障碍物就不用赋值了else dp[i][j] = dp[i-1][j] + dp[i][j-1]; }}return dp[m-1][n-1];}
};

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

js案例:1.简单计算器

目录 一.效果图 二.实现思路 整体思路 ​ 1.关键是dom操作 ​ 2.设置点击事件 3.数据类型的隐式转换和赋值 三.完整代码 一.效果图 二.实现思路 整体思路 1.关键是dom操作 通过 document.getElementById(id) 获取html中的dom元素 每一个html标签都是一个对象&…

CANoe通过Frame Histogram窗口统计报文周期(方便快捷)

文章目录 效果展示1.插入Frame Histogram窗口2.Activate3.运行CANoe&#xff0c;停止后查看write窗口 效果展示 统计报文周期信息输出在write窗口。 1.插入Frame Histogram窗口 2.Activate 3.运行CANoe&#xff0c;停止后查看write窗口 统计报文周期信息输出在write窗口。

Pytorch深度学习-----神经网络模型的保存与加载(VGG16模型)

系列文章目录 PyTorch深度学习——Anaconda和PyTorch安装 Pytorch深度学习-----数据模块Dataset类 Pytorch深度学习------TensorBoard的使用 Pytorch深度学习------Torchvision中Transforms的使用&#xff08;ToTensor&#xff0c;Normalize&#xff0c;Resize &#xff0c;Co…

数据结构刷题训练——链表篇(一)

目录 前言 题目一&#xff1a;链表的中间节点 思路 分析 题解 题目二&#xff1a;链表中倒数第k个结点 思路 分析 题解 题目三&#xff1a;合并两个有序链表 思路 分析 题解 方法二 题解 题目四&#xff1a;链表的回文结构 思路 分析 题解 总结 前言 今天我将开…

2023华数杯C题总结

前言 对这次比赛中遇到的问题和卡住的思路进行复盘&#xff0c;整理相关心得&#xff0c;供以后比赛参考 &#x1f9e1;1.认识数据类型&#x1f9e1; 连续变量&#xff1a;母亲年龄、妊娠时间、CBTS、EPDS、HADS、整晚睡醒时间、婴儿年龄 无序分类变量&#xff1a;婚姻状态、…

Gpt微信小程序搭建的前后端流程 - 前端小程序部分-2.确定交互所需的后端API(二)

Gpt微信小程序搭建的前后端流程 - 前端小程序部分-2.确定交互所需的后端API(二) 参考微信小程序-小柠AI智能聊天&#xff0c;可自行先体验。 根据上一节的小程序静态页面设计&#xff0c;需要从后端获取数据的主要4个点&#xff1a; 登录流程&#xff1b;获取今日已提问次数&a…

Unity制作护盾——2、力场冲击波护盾

Unity制作力场护盾 大家好&#xff0c;我是阿赵。   继续做护盾&#xff0c;这一期做一个力场冲击波护盾。 一、效果展示 主要的效果并不是这个球&#xff0c;而是护盾在被攻击的时候&#xff0c;会出现一个扩散的冲击波。比如上图在右边出现了冲击波 如果在左边被攻击&am…

MongoDB 6.0.8 安装配置

一、前言 MongoDB是一个基于分布式文件存储的数据库。由C语言编写。旨在为WEB应用提供可扩展的高性能数据存储解决方案。在高负载的情况下&#xff0c;添加更多的节点&#xff0c;可以保证服务器性能。 MongoDB 将数据存储为一个文档&#xff0c;数据结构由键值(key>value…

[分享]STM32G070 串口 乱码 解决方法

硬件 NUCLEO-G070RB 工具 cubemx 解决方法 7bit 改为 8bit printf 配置方法 添加头文件 #include <stdio.h> 添加重定向代码 #ifdef __GNUC__#define PUTCHAR_PROTOTYPE int __io_putchar(int ch)#else#define PUTCHAR_PROTOTYPE int fputc(int ch, FILE *f)#endi…

卷积神经网络实现MNIST手写数字识别 - P1

&#x1f368; 本文为&#x1f517;365天深度学习训练营 中的学习记录博客&#x1f366; 参考文章&#xff1a;365天深度学习训练营-第P1周&#xff1a;实现mnist手写数字识别&#x1f356; 原作者&#xff1a;K同学啊 | 接辅导、项目定制&#x1f680; 文章来源&#xff1a;K同…

SPM(Swift Package Manager)开发及常见事项

SPM怎么使用的不再赘述&#xff0c;其优点是Cocoapods这样的远古产物难以望其项背的&#xff0c;而且最重要的是可二进制化、对xcproj项目无侵入&#xff0c;除了网络之外简直就是为团队开发的项目库依赖最好的管理工具&#xff0c;是时候抛弃繁杂低下的cocoapods了。 一&…

C语言:打开调用堆栈

第一步&#xff1a;打断点 第二步&#xff1a;FnF5 第三步&#xff1a;按如图找到调用堆栈

使用Flask.Request的方法和属性,获取get和post请求参数(二)

1、Flask中的request 在Python发送Post、Get等请求时&#xff0c;我们使用到requests库。Flask中有一个request库&#xff0c;有其特有的一些方法和属性&#xff0c;注意跟requests不是同一个。 2、Post请求&#xff1a;request.get_data() 用于服务端获取客户端请求数据。注…

积累常见的有针对性的python面试题---python面试题001

1.考点列表的.remove方法的参数是传入的对应的元素的值,而不是下标 然后再看remove这里,注意这个是,删除写的那个值,比如这里写3,就是删除3, 而不是下标. remove不是下标删除,而是内容删除. 2.元组操作,元组不支持修改,某个下标的内容 可以问他如何修改元组的某个元素 3.…

【MMU】认识 MMU 及内存映射的流程

MMU&#xff08;Memory Manager Unit&#xff09;&#xff0c;是内存管理单元&#xff0c;负责将虚拟地址转换成物理地址。除此之外&#xff0c;MMU 实现了内存保护&#xff0c;进程无法直接访问物理内存&#xff0c;防止内存数据被随意篡改。 目录 一、内存管理体系结构 1、…

idea打开多个项目需要开多个窗口(恢复询问弹窗)

【版权所有&#xff0c;文章允许转载&#xff0c;但须以链接方式注明源地址&#xff0c;否则追究法律责任】【创作不易&#xff0c;点个赞就是对我最大的支持】 前言 仅作为学习笔记&#xff0c;供大家参考 总结的不错的话&#xff0c;记得点赞收藏关注哦&#xff01; 使用…

【TypeScript】中定义与使用 Class 类的解读理解

目录 类的概念类的继承 &#xff1a;类的存取器&#xff1a;类的静态方法与静态属性&#xff1a;类的修饰符&#xff1a;参数属性&#xff1a;抽象类&#xff1a;类的类型: 总结&#xff1a; 类的概念 类是用于创建对象的模板。他们用代码封装数据以处理该数据。JavaScript 中的…

一起学SF框架系列7.1-spring-AOP-基础知识

AOP(Aspect-oriented Programming-面向切面编程&#xff09;是一种编程模式&#xff0c;是对OOP(Object-oriented Programming-面向对象编程&#xff09;一种有益补充。在OOP中&#xff0c;万事万物都是独立的对象&#xff0c;对象相互耦合关系是基于业务进行的&#xff1b;但在…

MySQL之深入InnoDB存储引擎——Undo页

文章目录 一、UNDO日志格式1、INSERT操作对应的UNDO日志2、DELETE操作对应的undo日志3、UPDATE操作对应的undo日志1&#xff09;不更新主键2&#xff09;更新主键的操作 3、增删改操作对二级索引的影响 二、UNDO页三、UNDO页面链表四、undo日志具体写入过程五、回滚段1、回滚段…

C语言系列之原码、反码和补码

一.欢迎来到我的酒馆 讨论c语言中&#xff0c;原码、反码、补码。 目录 一.欢迎来到我的酒馆二.原码 二.原码 2.1在计算机中&#xff0c;所有数据都是以二进制存储的&#xff0c;但不是直接存储二进制数&#xff0c;而是存储二进制的补码。原码很好理解&#xff0c;就是对应的…