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];}
};
相关文章:
leetcode 63. 不同路径 II
2023.8.9 这题是不同路径I的升级版,在路径上增加了障碍物,有障碍物的地方无法通过。 我的思路依然还是使用动态规划,dp[i][j]的含义依然是到(i,j)这个位置的路径个数。只需要在dp数组中将有障碍物的地方赋为…...
c语言每日一练(5)
前言:每日一练系列,每一期都包含5道选择题,2道编程题,博主会尽可能详细地进行讲解,令初学者也能听的清晰。每日一练系列会持续更新,暑假时三天之内必有一更,到了开学之后,将看学业情…...
pycharm配置conda虚拟环境
📕作者简介:热编程的贝贝,致力于C/C、Java、Python等多编程语言,热爱跑步健身,喜爱音乐的一位博主。 📗本文收录于贝贝的日常汇报系列,大家有兴趣的可以看一看 📘相关专栏深度学习、…...
ubuntu 如何命令行打开系统设置(Wifi,网络,应用程序...)
关于GNOME GNOME 是一个自由、开放源代码的桌面环境,它运行在 Linux 和其他类 UNIX 操作系统上。它是 GNU 项目的一部分,旨在为 Linux 操作系统提供一个现代化、易于使用的用户界面。 GNOME 桌面环境包括许多应用程序,例如文件管理器、文本编…...
MySQL DQL 数据查询
文章目录 1.SELECT 语句2.SELECT 子句3.FROM 子句4.WHERE 子句5.GROUP BY 子句6.HAVING 子句7.ORDER BY 子句8.LIMIT 子句9.DISTINCT 子句10.JOIN 子句11.UNION 子句12.查看数据表记录数13.检查查询语句的执行效率14.查看 SQL 执行时的警告参考文献 1.SELECT 语句 MySQL 的 SE…...
深度学习基础知识笔记
深度学习要解决的问题 1 深度学习要解决的问题2 应用领域3 计算机视觉任务4 视觉任务中遇到的问题5 得分函数6 损失函数7 前向传播整体流程8 返向传播计算方法1 梯度下降 9 神经网络整体架构11 神经元个数对结果的影响12 正则化和激活函数1 正则化2 激活函数 13 神经网络过拟合…...
怎么系统的学习机器学习、深度学习?当然是看书了
目录 前言 内容简介 学完本书,你将能够 作者简介 本书目录 京东自购链接 前言 近年来,机器学习方法凭借其理解海量数据和自主决策的能力,已在医疗保健、 机器人、生物学、物理学、大众消费和互联网服务等行业得到了广泛的应用。自从Ale…...
无涯教程-Perl - binmode函数
描述 此函数设置在区分两者的操作系统上以二进制形式读取和写入FILEHANDLE的格式。非二进制文件的CR LF序列在输入时转换为LF,在LF时在输出时转换为CR LF。这对于使用两个字符分隔文本文件中的行的操作系统(MS-DOS)至关重要,但对使用单个字符的操作系统(Unix,Mac OS,QNX)没有影…...
Spring Boot Maven package时显式的跳过test内容
在pom.xml的编译插件部分显式的增加一段内容: <plugin> <!-- maven打包时,显式的跳过test部分 --><groupId>org.apache.maven.plugins</groupId><artifactId>maven-surefire-plugin</artifactId><version>3.…...
排序算法————基数排序(RadixSort)
基数排序的概念: 什么是基数排序???基数排序是一种和快排、归并、希尔等等不一样的排序...它不需要比较和移动就可以完成整型的排序。它是时间复杂度是O(K*N),空间复杂度是O(KM&…...
leetcode做题笔记75颜色分类
给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums ,原地对它们进行排序,使得相同颜色的元素相邻,并按照红色、白色、蓝色顺序排列。 我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。 必须在不使用库内置的 sort 函数的情况下解决…...
聊一下互联网开源变现
(点击即可收听) 互联网开源变现其实是指通过开源软件或者开放源代码的方式,实现收益或盈利。这种方式越来越被广泛应用于互联网行业 在互联网开源变现的模式中,最常见的方式是通过捐款、广告、付费支持或者授权等方式获利。 例如,有些开源软件…...
PHP日期差计算器,计算两个时间相差 年/月/日
1. 计算两个日期相隔多少年,多少月,多少天示例:laravel框架实现 /*** 天数计算* return \Illuminate\Http\JsonResponse*/public function loveDateCal(){$start_date $this->request(start_date);$end_date $this->request(end_date…...
20230812在WIN10下使用python3将SRT格式的字幕转换为SSA格式
20230812在WIN10下使用python3将SRT格式的字幕转换为SSA格式 2023/8/12 20:58 本文的SSA格式以【Batch Subtitles Converter(批量字幕转换) v1.23】的格式为准! 1、 缘起:网上找到的各种各样的字幕转换软件/小工具都不是让自己完全满意! 【都…...
matlab使用教程(13)—稀疏矩阵创建和使用
使用稀疏矩阵存储包含众多零值元素的数据,可以节省大量内存并加快该数据的处理速度。sparse 是一种属性,可以将该属性分配给由 double 或 logical 元素组成的任何二维 MATLAB 矩阵。通过 sparse 属性,MATLAB 可以: • 仅存储矩…...
UI美工设计的主要职责(合集)
UI美工设计的主要职责1 职责: 1、执行公司的规章制度及专业管理办法; 2、 负责重点项目的原型设计和产品流程设计、视觉设计,优化网站和移动端的设计流程和规范,制定产品 UI/UE规范及文档编写; 3、负责使用PS、AI、illustrator、MarkMan、…...
【前端二次开发框架关于关闭eslint】
前端二次开发框架关于关闭eslint 方法一方法二方法三方法四:以下是若想要关闭项目中的部分代码时: 方法一 在vue.config.js里面进行配置: module.exports {lintOnSave:false,//是否开启eslint保存检测 ,它的有效值为 true || false || err…...
Scractch3.0_Arduino_ESP32_学习随记_蓝牙键盘(三)
C02蓝牙键盘 目的器材程序联系我们 目的 通过C02实现蓝牙键盘 器材 硬件: 齐护机器人C02 购买地址 软件: scratch3.0 下载地址:官网下载 程序 在P5口连接按钮模块。 蓝牙键盘组合按键动作的实现。 当对应按键按下时模拟键盘动作,先按下ctrl然后按下对应组合键…...
Spark2.2出现异常:ERROR SparkUI: Failed to bind SparkUI
详细错误信息如下: 复制代码 19/03/19 11:04:18 INFO util.log: Logging initialized 5402ms 19/03/19 11:04:18 INFO server.Server: jetty-9.3.z-SNAPSHOT 19/03/19 11:04:18 INFO server.Server: Started 5604ms 19/03/19 11:04:18 WARN util.Utils: Service ‘S…...
LeetCode 2811. Check if it is Possible to Split Array【脑筋急转弯;前缀和+动态规划或记忆化DFS】中等
本文属于「征服LeetCode」系列文章之一,这一系列正式开始于2021/08/12。由于LeetCode上部分题目有锁,本系列将至少持续到刷完所有无锁题之日为止;由于LeetCode还在不断地创建新题,本系列的终止日期可能是永远。在这一系列刷题文章…...
Vue记事本应用实现教程
文章目录 1. 项目介绍2. 开发环境准备3. 设计应用界面4. 创建Vue实例和数据模型5. 实现记事本功能5.1 添加新记事项5.2 删除记事项5.3 清空所有记事 6. 添加样式7. 功能扩展:显示创建时间8. 功能扩展:记事项搜索9. 完整代码10. Vue知识点解析10.1 数据绑…...
SciencePlots——绘制论文中的图片
文章目录 安装一、风格二、1 资源 安装 # 安装最新版 pip install githttps://github.com/garrettj403/SciencePlots.git# 安装稳定版 pip install SciencePlots一、风格 简单好用的深度学习论文绘图专用工具包–Science Plot 二、 1 资源 论文绘图神器来了:一行…...
在鸿蒙HarmonyOS 5中实现抖音风格的点赞功能
下面我将详细介绍如何使用HarmonyOS SDK在HarmonyOS 5中实现类似抖音的点赞功能,包括动画效果、数据同步和交互优化。 1. 基础点赞功能实现 1.1 创建数据模型 // VideoModel.ets export class VideoModel {id: string "";title: string ""…...
sipsak:SIP瑞士军刀!全参数详细教程!Kali Linux教程!
简介 sipsak 是一个面向会话初始协议 (SIP) 应用程序开发人员和管理员的小型命令行工具。它可以用于对 SIP 应用程序和设备进行一些简单的测试。 sipsak 是一款 SIP 压力和诊断实用程序。它通过 sip-uri 向服务器发送 SIP 请求,并检查收到的响应。它以以下模式之一…...
AI病理诊断七剑下天山,医疗未来触手可及
一、病理诊断困局:刀尖上的医学艺术 1.1 金标准背后的隐痛 病理诊断被誉为"诊断的诊断",医生需通过显微镜观察组织切片,在细胞迷宫中捕捉癌变信号。某省病理质控报告显示,基层医院误诊率达12%-15%,专家会诊…...
【从零学习JVM|第三篇】类的生命周期(高频面试题)
前言: 在Java编程中,类的生命周期是指类从被加载到内存中开始,到被卸载出内存为止的整个过程。了解类的生命周期对于理解Java程序的运行机制以及性能优化非常重要。本文会深入探寻类的生命周期,让读者对此有深刻印象。 目录 …...
群晖NAS如何在虚拟机创建飞牛NAS
套件中心下载安装Virtual Machine Manager 创建虚拟机 配置虚拟机 飞牛官网下载 https://iso.liveupdate.fnnas.com/x86_64/trim/fnos-0.9.2-863.iso 群晖NAS如何在虚拟机创建飞牛NAS - 个人信息分享...
日常一水C
多态 言简意赅:就是一个对象面对同一事件时做出的不同反应 而之前的继承中说过,当子类和父类的函数名相同时,会隐藏父类的同名函数转而调用子类的同名函数,如果要调用父类的同名函数,那么就需要对父类进行引用&#…...
MySQL 主从同步异常处理
阅读原文:https://www.xiaozaoshu.top/articles/mysql-m-s-update-pk MySQL 做双主,遇到的这个错误: Could not execute Update_rows event on table ... Error_code: 1032是 MySQL 主从复制时的经典错误之一,通常表示ÿ…...
数学建模-滑翔伞伞翼面积的设计,运动状态计算和优化 !
我们考虑滑翔伞的伞翼面积设计问题以及运动状态描述。滑翔伞的性能主要取决于伞翼面积、气动特性以及飞行员的重量。我们的目标是建立数学模型来描述滑翔伞的运动状态,并优化伞翼面积的设计。 一、问题分析 滑翔伞在飞行过程中受到重力、升力和阻力的作用。升力和阻力与伞翼面…...
