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还在不断地创建新题,本系列的终止日期可能是永远。在这一系列刷题文章…...
理解 MCP 工作流:使用 Ollama 和 LangChain 构建本地 MCP 客户端
🌟 什么是 MCP? 模型控制协议 (MCP) 是一种创新的协议,旨在无缝连接 AI 模型与应用程序。 MCP 是一个开源协议,它标准化了我们的 LLM 应用程序连接所需工具和数据源并与之协作的方式。 可以把它想象成你的 AI 模型 和想要使用它…...
LeetCode - 394. 字符串解码
题目 394. 字符串解码 - 力扣(LeetCode) 思路 使用两个栈:一个存储重复次数,一个存储字符串 遍历输入字符串: 数字处理:遇到数字时,累积计算重复次数左括号处理:保存当前状态&a…...
【配置 YOLOX 用于按目录分类的图片数据集】
现在的图标点选越来越多,如何一步解决,采用 YOLOX 目标检测模式则可以轻松解决 要在 YOLOX 中使用按目录分类的图片数据集(每个目录代表一个类别,目录下是该类别的所有图片),你需要进行以下配置步骤&#x…...
C++中string流知识详解和示例
一、概览与类体系 C 提供三种基于内存字符串的流,定义在 <sstream> 中: std::istringstream:输入流,从已有字符串中读取并解析。std::ostringstream:输出流,向内部缓冲区写入内容,最终取…...
ardupilot 开发环境eclipse 中import 缺少C++
目录 文章目录 目录摘要1.修复过程摘要 本节主要解决ardupilot 开发环境eclipse 中import 缺少C++,无法导入ardupilot代码,会引起查看不方便的问题。如下图所示 1.修复过程 0.安装ubuntu 软件中自带的eclipse 1.打开eclipse—Help—install new software 2.在 Work with中…...
多种风格导航菜单 HTML 实现(附源码)
下面我将为您展示 6 种不同风格的导航菜单实现,每种都包含完整 HTML、CSS 和 JavaScript 代码。 1. 简约水平导航栏 <!DOCTYPE html> <html lang"zh-CN"> <head><meta charset"UTF-8"><meta name"viewport&qu…...
什么?连接服务器也能可视化显示界面?:基于X11 Forwarding + CentOS + MobaXterm实战指南
文章目录 什么是X11?环境准备实战步骤1️⃣ 服务器端配置(CentOS)2️⃣ 客户端配置(MobaXterm)3️⃣ 验证X11 Forwarding4️⃣ 运行自定义GUI程序(Python示例)5️⃣ 成功效果
利用Hbuilder 创建项目 运行到内置浏览器看效果 下载微信小程序 安装到Hbuilder 下载地址 :开发者工具默认安装 设置服务端口号 在Hbuilder中设置微信小程序 配置 找到运行设置,将微信开发者工具放入到Hbuilder中, 打开后出现 如下 bug 解…...
