当前位置: 首页 > 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来添加数据标签和数值显示到统…...

后进先出(LIFO)详解

LIFO 是 Last In, First Out 的缩写&#xff0c;中文译为后进先出。这是一种数据结构的工作原则&#xff0c;类似于一摞盘子或一叠书本&#xff1a; 最后放进去的元素最先出来 -想象往筒状容器里放盘子&#xff1a; &#xff08;1&#xff09;你放进的最后一个盘子&#xff08…...

RestClient

什么是RestClient RestClient 是 Elasticsearch 官方提供的 Java 低级 REST 客户端&#xff0c;它允许HTTP与Elasticsearch 集群通信&#xff0c;而无需处理 JSON 序列化/反序列化等底层细节。它是 Elasticsearch Java API 客户端的基础。 RestClient 主要特点 轻量级&#xff…...

Vue记事本应用实现教程

文章目录 1. 项目介绍2. 开发环境准备3. 设计应用界面4. 创建Vue实例和数据模型5. 实现记事本功能5.1 添加新记事项5.2 删除记事项5.3 清空所有记事 6. 添加样式7. 功能扩展&#xff1a;显示创建时间8. 功能扩展&#xff1a;记事项搜索9. 完整代码10. Vue知识点解析10.1 数据绑…...

【杂谈】-递归进化:人工智能的自我改进与监管挑战

递归进化&#xff1a;人工智能的自我改进与监管挑战 文章目录 递归进化&#xff1a;人工智能的自我改进与监管挑战1、自我改进型人工智能的崛起2、人工智能如何挑战人类监管&#xff1f;3、确保人工智能受控的策略4、人类在人工智能发展中的角色5、平衡自主性与控制力6、总结与…...

python/java环境配置

环境变量放一起 python&#xff1a; 1.首先下载Python Python下载地址&#xff1a;Download Python | Python.org downloads ---windows -- 64 2.安装Python 下面两个&#xff0c;然后自定义&#xff0c;全选 可以把前4个选上 3.环境配置 1&#xff09;搜高级系统设置 2…...

服务器硬防的应用场景都有哪些?

服务器硬防是指一种通过硬件设备层面的安全措施来防御服务器系统受到网络攻击的方式&#xff0c;避免服务器受到各种恶意攻击和网络威胁&#xff0c;那么&#xff0c;服务器硬防通常都会应用在哪些场景当中呢&#xff1f; 硬防服务器中一般会配备入侵检测系统和预防系统&#x…...

2021-03-15 iview一些问题

1.iview 在使用tree组件时&#xff0c;发现没有set类的方法&#xff0c;只有get&#xff0c;那么要改变tree值&#xff0c;只能遍历treeData&#xff0c;递归修改treeData的checked&#xff0c;发现无法更改&#xff0c;原因在于check模式下&#xff0c;子元素的勾选状态跟父节…...

css的定位(position)详解:相对定位 绝对定位 固定定位

在 CSS 中&#xff0c;元素的定位通过 position 属性控制&#xff0c;共有 5 种定位模式&#xff1a;static&#xff08;静态定位&#xff09;、relative&#xff08;相对定位&#xff09;、absolute&#xff08;绝对定位&#xff09;、fixed&#xff08;固定定位&#xff09;和…...

ip子接口配置及删除

配置永久生效的子接口&#xff0c;2个IP 都可以登录你这一台服务器。重启不失效。 永久的 [应用] vi /etc/sysconfig/network-scripts/ifcfg-eth0修改文件内内容 TYPE"Ethernet" BOOTPROTO"none" NAME"eth0" DEVICE"eth0" ONBOOT&q…...

让回归模型不再被异常值“带跑偏“,MSE和Cauchy损失函数在噪声数据环境下的实战对比

在机器学习的回归分析中&#xff0c;损失函数的选择对模型性能具有决定性影响。均方误差&#xff08;MSE&#xff09;作为经典的损失函数&#xff0c;在处理干净数据时表现优异&#xff0c;但在面对包含异常值的噪声数据时&#xff0c;其对大误差的二次惩罚机制往往导致模型参数…...