【力扣】63. 不同路径 II <动态规划>
【力扣】63. 不同路径 II
一个机器人位于一个 m m m x n n n 网格的左上角 (起始点在下图中标记为 “Start” )。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为 “Finish”)。
现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径?网格中的障碍物和空位置分别用 1 和 0 来表示。
示例 1:
起点 | 0 | 0 |
---|---|---|
0 | 障碍 | 0 |
0 | 0 | 终点 |
输入:obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
输出:2
解释:3x3 网格的正中间有一个障碍物。
从左上角到右下角一共有 2 条不同的路径:
-
- 向右 -> 向右 -> 向下 -> 向下
-
- 向下 -> 向下 -> 向右 -> 向右
示例 2:
起点 | 障碍 |
---|---|
0 | 终点 |
输入:obstacleGrid = [[0,1],[0,0]]
输出:1
提示:
m == obstacleGrid.length
n == obstacleGrid[i].length
1 <= m, n <= 100
obstacleGrid[i][j] 为 0 或 1
题解
- 确定 dp 数组以及下标的含义
dp[i][j] :表示从 (0,0) 出发,到 (i, j) 有 dp[i][j] 条不同的路径。 - 确定递推公式
想要求 dp[i][j],只能有两个方向来推导出来,即 dp[i - 1][j] 和 dp[i][j - 1]。
dp[i - 1][j] 表示是从 (0, 0) 的位置到 (i - 1, j) 有几条路径,dp[i][j - 1]同理
dp[i][j] = dp[i - 1][j] + dp[i][j - 1],因为 dp[i][j] 只有这两个方向过来。
因为有了障碍,(i, j) 如果就是障碍的话应该就保持初始状态(初始状态为0)。 - dp 数组如何初始化
dp[i][0] 一定都是1,因为从 (0, 0) 的位置到 (i, 0) 的路径只有一条,那么 dp[0][j] 也同理。
但如果 (i, 0) 这条边有了障碍之后,障碍之后(包括障碍)都是走不到的位置了,所以障碍之后的 dp[i][0] 应该还是初始值0。下标(0, j)的初始化情况同理。 - 确定遍历顺序
dp[i][j] 都是从其上方和左方推导而来 - 举例推导 dp 数组(打印 dp 数组)
public class Solution {public int uniquePathsWithObstacles(int[][] obstacleGrid) {int m = obstacleGrid.length;int n = obstacleGrid[0].length;int[][] dp = new int[m][n];//如果在起点或终点出现了障碍,直接返回0if (obstacleGrid[m - 1][n - 1] == 1 || obstacleGrid[0][0] == 1) {return 0;}//dp数组初始化,若有障碍,后面都是0for (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++) {dp[i][j] = (obstacleGrid[i][j] == 0) ? dp[i - 1][j] + dp[i][j - 1] : 0;}}return dp[m - 1][n - 1];}
}
相关文章:
【力扣】63. 不同路径 II <动态规划>
【力扣】63. 不同路径 II 一个机器人位于一个 m m m x n n n 网格的左上角 (起始点在下图中标记为 “Start” )。 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为 “Finish”)。 现在考虑网格…...

【Linux】JumpServer 堡垒机远程访问
文章目录 前言1. 安装Jump server2. 本地访问jump server3. 安装 cpolar内网穿透软件4. 配置Jump server公网访问地址5. 公网远程访问Jump server6. 固定Jump server公网地址 前言 JumpServer 是广受欢迎的开源堡垒机,是符合 4A 规范的专业运维安全审计系统。JumpS…...

WebGPT VS WebGPU
推荐:使用 NSDT编辑器 快速搭建3D应用场景 随着WebGPU的引入,Web开发发生了有趣的转变,WebGPU是一种新的API,允许Web应用程序直接访问设备的图形处理单元(GPU)。这种发展意义重大,因为 GPU 擅长…...

【Flutter】Flutter 使用 collection 优化集合操作
【Flutter】Flutter 使用 collection 优化集合操作 文章目录 一、前言二、安装和基本使用三、算法介绍四、如何定义相等性五、Iterable Zip 的使用六、优先队列的实现和应用七、包装器的使用八、完整示例九、总结 一、前言 大家好!我是小雨青年,今天我要…...

【核心复现】基于合作博弈的综合能源系统电-热-气协同优化运行策略(Matlab代码实现)
💥💥💞💞欢迎来到本博客❤️❤️💥💥 🏆博主优势:🌞🌞🌞博客内容尽量做到思维缜密,逻辑清晰,为了方便读者。 ⛳️座右铭&a…...
【设计模式】Head First 设计模式——抽象工厂模式 C++实现
设计模式最大的作用就是在变化和稳定中间寻找隔离点,然后分离它们,从而管理变化。将变化像小兔子一样关到笼子里,让它在笼子里随便跳,而不至于跳出来把你整个房间给污染掉。 设计思想 提供一个接口,让该接口负责创建一…...

pdf怎么转换成jpg图片?
随着数字文档的广泛应用,将PDF转换为JPG图片格式成为了一个常见的需求。无论是为了在网页上展示内容,还是为了与他人分享图片,以下是一些简单的方法,帮助您将PDF文件快速转换为高质量的JPG图片。 方法一:在线PDF转JPG…...

远程访问Linux的DataEase数据可视化分析,有哪些推荐的工具?
DataEase 是开源的数据可视化分析工具,帮助用户快速分析数据并洞察业务趋势,从而实现业务的改进与优化。是开源的数据可视化分析工具,帮助用户快速分析数据并洞察业务趋势,从而实现业务的改进与优化。 在本地搭建后,借助cpolar 内…...

每日一题——旋转图像
旋转图像 题目链接 方法一:利用辅助数组 通过对示例的观察和分析,我们可以得到这样的结论: 对于原数组的下标为i行元素,顺时针旋转九十度后,都变成了下标为(n-1-i)列元素。如图所示ÿ…...
「Docker」《入门Docker:解放部署烦恼,提高开发效率》
《入门Docker:解放部署烦恼,提高开发效率》 一、引言1.1 Docker的定义和概念1.2 Docker的优势和应用场景 二、Docker基础知识2.1 Docker架构和组件2.2 Docker镜像和容器的关系2.3 Docker仓库和镜像的管理 三、安装和配置Docker环境3.1 安装Docker引擎3.2…...
数据结构--5.3图的遍历(广度优先遍历)
广度优先遍历: 广度优先遍历(BreadthFirstSearch),又称为广度优先搜索,简称BFS。 要实现对图的广度遍历,我们可以利用队列来实现。 void BFSTraverse(MGraph G) {int i,j;Queue Q;for(i0;i<G.numVerte…...

SQL注入漏洞复现(CVE-2017-8917)
文章目录 搭建环境启动环境漏洞复现报错注入使用sqlmap 前提条件: 1.安装docker docker pull medicean/vulapps:j_joomla_22.安装docker-compose docker run -d -p 8000:80 medicean/vulapps:j_joomla_23.下载vulhub Docker Compose是 docker 提供的一个命令行工具&…...

Http 1.0 1.1 2.0 3.0 版本差别
Http 1.0 发布年份:1996 非官方标准 短链接:每一次请求都对应一次TCP的连接与释放 开销大:每次请求都要TCP的连接与释放队头阻塞:每次请求都必须等上一次请求获得响应之后,才可以发送;效率低下 缓存&…...
javaee spring 依赖注入之复杂类型的注入数组 集合 等
spring 依赖注入之复杂类型的注入 package com.test.pojo;import java.util.List; import java.util.Map; import java.util.Properties;/*** description:* projectName:testSpring* see:com.test.pojo* createTime:2023/8/27 14:39*/ public class AA {private int[] arr;pr…...

[Android AIDL] --- AIDL工程搭建
0 AIDL概念 AIDL(Android Interface Definition Language)是一种 IDL 语言,用于生成可以在 Android 设备上两个进程之间进行进程间通信(IPC)的代码。 通过 AIDL,可以在一个进程中获取另一个进程的数据和调…...

正中优配:回购!回购!再回购!已成A股新常态?
上市公司回购潮还在继续! 8月30日,海通证券、捷佳伟创等多家上市公司纷繁发布回购公告。自8月18日证监会提出“放宽相关回购条件,支撑上市公司展开股份回购”以来,A股上市公司掀起了一轮“回购潮”。Wind数据显现,8月…...

C# 多线程交替按照指定顺序执行
1.关于AutoResetEvent和ManualResetEvent的区别解释如下: AutoResetEvent和ManualResetEvent是.NET中的两个线程同步类。它们之间的主要区别在于其释放信号的方式以及对等待线程的影响。 AutoResetEvent的作用是在等待的线程被信号唤醒后,将信号自动重…...

【VLDB 2023】基于预测的云资源弹性伸缩框架MagicScaler,实现“高QoS,低成本”双丰收
开篇 近日,由阿里云计算平台大数据基础工程技术团队主导,与计算平台MaxCompute团队、华东师范大学数据科学与工程学院、达摩院合作,基于预测的云计算平台资源弹性伸缩框架论文《MagicScaler: Uncertainty-aware, Predictive Autoscaling 》被…...

Node爬虫项目精简版 wallhaven网站实操 2023.8.29
练习地址: https://wallhaven.cc/toplist const express require(express); const axios require(axios); const cheerio require(cheerio); const schedule require(node-schedule); const fs require(fs);async function downloadImage(url) {const response…...
Vue统计图表的数据标签和数值显示技巧
Vue统计图表的数据标签和数值显示技巧 在开发Web应用程序时,统计图表是非常重要的数据呈现方式。Vue是一种流行的JavaScript框架,它提供了许多方便的功能来处理和展示数据。在这篇文章中,我们将探讨如何使用Vue来添加数据标签和数值显示到统…...

LBE-LEX系列工业语音播放器|预警播报器|喇叭蜂鸣器的上位机配置操作说明
LBE-LEX系列工业语音播放器|预警播报器|喇叭蜂鸣器专为工业环境精心打造,完美适配AGV和无人叉车。同时,集成以太网与语音合成技术,为各类高级系统(如MES、调度系统、库位管理、立库等)提供高效便捷的语音交互体验。 L…...

【WiFi帧结构】
文章目录 帧结构MAC头部管理帧 帧结构 Wi-Fi的帧分为三部分组成:MAC头部frame bodyFCS,其中MAC是固定格式的,frame body是可变长度。 MAC头部有frame control,duration,address1,address2,addre…...

(二)TensorRT-LLM | 模型导出(v0.20.0rc3)
0. 概述 上一节 对安装和使用有个基本介绍。根据这个 issue 的描述,后续 TensorRT-LLM 团队可能更专注于更新和维护 pytorch backend。但 tensorrt backend 作为先前一直开发的工作,其中包含了大量可以学习的地方。本文主要看看它导出模型的部分&#x…...

第一篇:Agent2Agent (A2A) 协议——协作式人工智能的黎明
AI 领域的快速发展正在催生一个新时代,智能代理(agents)不再是孤立的个体,而是能够像一个数字团队一样协作。然而,当前 AI 生态系统的碎片化阻碍了这一愿景的实现,导致了“AI 巴别塔问题”——不同代理之间…...
今日科技热点速览
🔥 今日科技热点速览 🎮 任天堂Switch 2 正式发售 任天堂新一代游戏主机 Switch 2 今日正式上线发售,主打更强图形性能与沉浸式体验,支持多模态交互,受到全球玩家热捧 。 🤖 人工智能持续突破 DeepSeek-R1&…...
Element Plus 表单(el-form)中关于正整数输入的校验规则
目录 1 单个正整数输入1.1 模板1.2 校验规则 2 两个正整数输入(联动)2.1 模板2.2 校验规则2.3 CSS 1 单个正整数输入 1.1 模板 <el-formref"formRef":model"formData":rules"formRules"label-width"150px"…...

Mac下Android Studio扫描根目录卡死问题记录
环境信息 操作系统: macOS 15.5 (Apple M2芯片)Android Studio版本: Meerkat Feature Drop | 2024.3.2 Patch 1 (Build #AI-243.26053.27.2432.13536105, 2025年5月22日构建) 问题现象 在项目开发过程中,提示一个依赖外部头文件的cpp源文件需要同步,点…...
ip子接口配置及删除
配置永久生效的子接口,2个IP 都可以登录你这一台服务器。重启不失效。 永久的 [应用] vi /etc/sysconfig/network-scripts/ifcfg-eth0修改文件内内容 TYPE"Ethernet" BOOTPROTO"none" NAME"eth0" DEVICE"eth0" ONBOOT&q…...
#Uniapp篇:chrome调试unapp适配
chrome调试设备----使用Android模拟机开发调试移动端页面 Chrome://inspect/#devices MuMu模拟器Edge浏览器:Android原生APP嵌入的H5页面元素定位 chrome://inspect/#devices uniapp单位适配 根路径下 postcss.config.js 需要装这些插件 “postcss”: “^8.5.…...

华为OD机考-机房布局
import java.util.*;public class DemoTest5 {public static void main(String[] args) {Scanner in new Scanner(System.in);// 注意 hasNext 和 hasNextLine 的区别while (in.hasNextLine()) { // 注意 while 处理多个 caseSystem.out.println(solve(in.nextLine()));}}priv…...