【力扣】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来添加数据标签和数值显示到统…...
java 实现excel文件转pdf | 无水印 | 无限制
文章目录 目录 文章目录 前言 1.项目远程仓库配置 2.pom文件引入相关依赖 3.代码破解 二、Excel转PDF 1.代码实现 2.Aspose.License.xml 授权文件 总结 前言 java处理excel转pdf一直没找到什么好用的免费jar包工具,自己手写的难度,恐怕高级程序员花费一年的事件,也…...

《用户共鸣指数(E)驱动品牌大模型种草:如何抢占大模型搜索结果情感高地》
在注意力分散、内容高度同质化的时代,情感连接已成为品牌破圈的关键通道。我们在服务大量品牌客户的过程中发现,消费者对内容的“有感”程度,正日益成为影响品牌传播效率与转化率的核心变量。在生成式AI驱动的内容生成与推荐环境中࿰…...
Qt Http Server模块功能及架构
Qt Http Server 是 Qt 6.0 中引入的一个新模块,它提供了一个轻量级的 HTTP 服务器实现,主要用于构建基于 HTTP 的应用程序和服务。 功能介绍: 主要功能 HTTP服务器功能: 支持 HTTP/1.1 协议 简单的请求/响应处理模型 支持 GET…...
高防服务器能够抵御哪些网络攻击呢?
高防服务器作为一种有着高度防御能力的服务器,可以帮助网站应对分布式拒绝服务攻击,有效识别和清理一些恶意的网络流量,为用户提供安全且稳定的网络环境,那么,高防服务器一般都可以抵御哪些网络攻击呢?下面…...
服务器--宝塔命令
一、宝塔面板安装命令 ⚠️ 必须使用 root 用户 或 sudo 权限执行! sudo su - 1. CentOS 系统: yum install -y wget && wget -O install.sh http://download.bt.cn/install/install_6.0.sh && sh install.sh2. Ubuntu / Debian 系统…...

网站指纹识别
网站指纹识别 网站的最基本组成:服务器(操作系统)、中间件(web容器)、脚本语言、数据厍 为什么要了解这些?举个例子:发现了一个文件读取漏洞,我们需要读/etc/passwd,如…...
C++.OpenGL (20/64)混合(Blending)
混合(Blending) 透明效果核心原理 #mermaid-svg-SWG0UzVfJms7Sm3e {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-SWG0UzVfJms7Sm3e .error-icon{fill:#552222;}#mermaid-svg-SWG0UzVfJms7Sm3e .error-text{fill…...

计算机基础知识解析:从应用到架构的全面拆解
目录 前言 1、 计算机的应用领域:无处不在的数字助手 2、 计算机的进化史:从算盘到量子计算 3、计算机的分类:不止 “台式机和笔记本” 4、计算机的组件:硬件与软件的协同 4.1 硬件:五大核心部件 4.2 软件&#…...

android13 app的触摸问题定位分析流程
一、知识点 一般来说,触摸问题都是app层面出问题,我们可以在ViewRootImpl.java添加log的方式定位;如果是touchableRegion的计算问题,就会相对比较麻烦了,需要通过adb shell dumpsys input > input.log指令,且通过打印堆栈的方式,逐步定位问题,并找到修改方案。 问题…...
精益数据分析(98/126):电商转化率优化与网站性能的底层逻辑
精益数据分析(98/126):电商转化率优化与网站性能的底层逻辑 在电子商务领域,转化率与网站性能是决定商业成败的核心指标。今天,我们将深入解析不同类型电商平台的转化率基准,探讨页面加载速度对用户行为的…...