当前位置: 首页 > news >正文

【力扣】63. 不同路径 II <动态规划>

【力扣】63. 不同路径 II

一个机器人位于一个 m m m x n n n 网格的左上角 (起始点在下图中标记为 “Start” )。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为 “Finish”)。
现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径?网格中的障碍物和空位置分别用 1 和 0 来表示。

示例 1:

起点00
0障碍0
00终点

输入:obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
输出:2
解释:3x3 网格的正中间有一个障碍物。
从左上角到右下角一共有 2 条不同的路径:

    1. 向右 -> 向右 -> 向下 -> 向下
    1. 向下 -> 向下 -> 向右 -> 向右

示例 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 网格的左上角 &#xff08;起始点在下图中标记为 “Start” &#xff09;。 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角&#xff08;在下图中标记为 “Finish”&#xff09;。 现在考虑网格…...

【Linux】JumpServer 堡垒机远程访问

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

WebGPT VS WebGPU

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

【Flutter】Flutter 使用 collection 优化集合操作

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

【核心复现】基于合作博弈的综合能源系统电-热-气协同优化运行策略(Matlab代码实现)

&#x1f4a5;&#x1f4a5;&#x1f49e;&#x1f49e;欢迎来到本博客❤️❤️&#x1f4a5;&#x1f4a5; &#x1f3c6;博主优势&#xff1a;&#x1f31e;&#x1f31e;&#x1f31e;博客内容尽量做到思维缜密&#xff0c;逻辑清晰&#xff0c;为了方便读者。 ⛳️座右铭&a…...

【设计模式】Head First 设计模式——抽象工厂模式 C++实现

设计模式最大的作用就是在变化和稳定中间寻找隔离点&#xff0c;然后分离它们&#xff0c;从而管理变化。将变化像小兔子一样关到笼子里&#xff0c;让它在笼子里随便跳&#xff0c;而不至于跳出来把你整个房间给污染掉。 设计思想 提供一个接口&#xff0c;让该接口负责创建一…...

pdf怎么转换成jpg图片?

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

远程访问Linux的DataEase数据可视化分析,有哪些推荐的工具?

DataEase 是开源的数据可视化分析工具&#xff0c;帮助用户快速分析数据并洞察业务趋势&#xff0c;从而实现业务的改进与优化。是开源的数据可视化分析工具&#xff0c;帮助用户快速分析数据并洞察业务趋势&#xff0c;从而实现业务的改进与优化。 在本地搭建后,借助cpolar 内…...

每日一题——旋转图像

旋转图像 题目链接 方法一&#xff1a;利用辅助数组 通过对示例的观察和分析&#xff0c;我们可以得到这样的结论&#xff1a; 对于原数组的下标为i行元素&#xff0c;顺时针旋转九十度后&#xff0c;都变成了下标为&#xff08;n-1-i&#xff09;列元素。如图所示&#xff…...

「Docker」《入门Docker:解放部署烦恼,提高开发效率》

《入门Docker&#xff1a;解放部署烦恼&#xff0c;提高开发效率》 一、引言1.1 Docker的定义和概念1.2 Docker的优势和应用场景 二、Docker基础知识2.1 Docker架构和组件2.2 Docker镜像和容器的关系2.3 Docker仓库和镜像的管理 三、安装和配置Docker环境3.1 安装Docker引擎3.2…...

数据结构--5.3图的遍历(广度优先遍历)

广度优先遍历&#xff1a; 广度优先遍历&#xff08;BreadthFirstSearch&#xff09;&#xff0c;又称为广度优先搜索&#xff0c;简称BFS。 要实现对图的广度遍历&#xff0c;我们可以利用队列来实现。 void BFSTraverse(MGraph G) {int i,j;Queue Q;for(i0;i<G.numVerte…...

SQL注入漏洞复现(CVE-2017-8917)

文章目录 搭建环境启动环境漏洞复现报错注入使用sqlmap 前提条件&#xff1a; 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 发布年份&#xff1a;1996 非官方标准 短链接&#xff1a;每一次请求都对应一次TCP的连接与释放 开销大&#xff1a;每次请求都要TCP的连接与释放队头阻塞&#xff1a;每次请求都必须等上一次请求获得响应之后&#xff0c;才可以发送&#xff1b;效率低下 缓存&…...

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&#xff08;Android Interface Definition Language&#xff09;是一种 IDL 语言&#xff0c;用于生成可以在 Android 设备上两个进程之间进行进程间通信&#xff08;IPC&#xff09;的代码。 通过 AIDL&#xff0c;可以在一个进程中获取另一个进程的数据和调…...

正中优配:回购!回购!再回购!已成A股新常态?

上市公司回购潮还在继续&#xff01; 8月30日&#xff0c;海通证券、捷佳伟创等多家上市公司纷繁发布回购公告。自8月18日证监会提出“放宽相关回购条件&#xff0c;支撑上市公司展开股份回购”以来&#xff0c;A股上市公司掀起了一轮“回购潮”。Wind数据显现&#xff0c;8月…...

C# 多线程交替按照指定顺序执行

1.关于AutoResetEvent和ManualResetEvent的区别解释如下&#xff1a; AutoResetEvent和ManualResetEvent是.NET中的两个线程同步类。它们之间的主要区别在于其释放信号的方式以及对等待线程的影响。 AutoResetEvent的作用是在等待的线程被信号唤醒后&#xff0c;将信号自动重…...

【VLDB 2023】基于预测的云资源弹性伸缩框架MagicScaler,实现“高QoS,低成本”双丰收

开篇 近日&#xff0c;由阿里云计算平台大数据基础工程技术团队主导&#xff0c;与计算平台MaxCompute团队、华东师范大学数据科学与工程学院、达摩院合作&#xff0c;基于预测的云计算平台资源弹性伸缩框架论文《MagicScaler: Uncertainty-aware, Predictive Autoscaling 》被…...

Node爬虫项目精简版 wallhaven网站实操 2023.8.29

练习地址&#xff1a; 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应用程序时&#xff0c;统计图表是非常重要的数据呈现方式。Vue是一种流行的JavaScript框架&#xff0c;它提供了许多方便的功能来处理和展示数据。在这篇文章中&#xff0c;我们将探讨如何使用Vue来添加数据标签和数值显示到统…...

java 实现excel文件转pdf | 无水印 | 无限制

文章目录 目录 文章目录 前言 1.项目远程仓库配置 2.pom文件引入相关依赖 3.代码破解 二、Excel转PDF 1.代码实现 2.Aspose.License.xml 授权文件 总结 前言 java处理excel转pdf一直没找到什么好用的免费jar包工具,自己手写的难度,恐怕高级程序员花费一年的事件,也…...

《用户共鸣指数(E)驱动品牌大模型种草:如何抢占大模型搜索结果情感高地》

在注意力分散、内容高度同质化的时代&#xff0c;情感连接已成为品牌破圈的关键通道。我们在服务大量品牌客户的过程中发现&#xff0c;消费者对内容的“有感”程度&#xff0c;正日益成为影响品牌传播效率与转化率的核心变量。在生成式AI驱动的内容生成与推荐环境中&#xff0…...

Qt Http Server模块功能及架构

Qt Http Server 是 Qt 6.0 中引入的一个新模块&#xff0c;它提供了一个轻量级的 HTTP 服务器实现&#xff0c;主要用于构建基于 HTTP 的应用程序和服务。 功能介绍&#xff1a; 主要功能 HTTP服务器功能&#xff1a; 支持 HTTP/1.1 协议 简单的请求/响应处理模型 支持 GET…...

高防服务器能够抵御哪些网络攻击呢?

高防服务器作为一种有着高度防御能力的服务器&#xff0c;可以帮助网站应对分布式拒绝服务攻击&#xff0c;有效识别和清理一些恶意的网络流量&#xff0c;为用户提供安全且稳定的网络环境&#xff0c;那么&#xff0c;高防服务器一般都可以抵御哪些网络攻击呢&#xff1f;下面…...

服务器--宝塔命令

一、宝塔面板安装命令 ⚠️ 必须使用 root 用户 或 sudo 权限执行&#xff01; sudo su - 1. CentOS 系统&#xff1a; yum install -y wget && wget -O install.sh http://download.bt.cn/install/install_6.0.sh && sh install.sh2. Ubuntu / Debian 系统…...

网站指纹识别

网站指纹识别 网站的最基本组成&#xff1a;服务器&#xff08;操作系统&#xff09;、中间件&#xff08;web容器&#xff09;、脚本语言、数据厍 为什么要了解这些&#xff1f;举个例子&#xff1a;发现了一个文件读取漏洞&#xff0c;我们需要读/etc/passwd&#xff0c;如…...

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、 计算机的应用领域&#xff1a;无处不在的数字助手 2、 计算机的进化史&#xff1a;从算盘到量子计算 3、计算机的分类&#xff1a;不止 “台式机和笔记本” 4、计算机的组件&#xff1a;硬件与软件的协同 4.1 硬件&#xff1a;五大核心部件 4.2 软件&#…...

android13 app的触摸问题定位分析流程

一、知识点 一般来说,触摸问题都是app层面出问题,我们可以在ViewRootImpl.java添加log的方式定位;如果是touchableRegion的计算问题,就会相对比较麻烦了,需要通过adb shell dumpsys input > input.log指令,且通过打印堆栈的方式,逐步定位问题,并找到修改方案。 问题…...

精益数据分析(98/126):电商转化率优化与网站性能的底层逻辑

精益数据分析&#xff08;98/126&#xff09;&#xff1a;电商转化率优化与网站性能的底层逻辑 在电子商务领域&#xff0c;转化率与网站性能是决定商业成败的核心指标。今天&#xff0c;我们将深入解析不同类型电商平台的转化率基准&#xff0c;探讨页面加载速度对用户行为的…...