学习记录:js算法(一百二十三):不同路径 II

文章目录

    • 不同路径 II
      • 思路一

不同路径 II

给定一个 m x n 的整数数组 grid。一个机器人初始位于 左上角(即 grid[0][0])。机器人尝试移动到 右下角(即 grid[m - 1][n - 1])。机器人每次只能向下或者向右移动一步。
网格中的障碍物和空位置分别用 1 和 0 来表示。机器人的移动路径中不能包含 任何 有障碍物的方格。
返回机器人能够到达右下角的不同路径数量。
测试用例保证答案小于等于 2 * 109。

图一:
在这里插入图片描述

图二:

在这里插入图片描述

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

思路一

function uniquePathsWithObstacles(obstacleGrid) {const m = obstacleGrid.length;const n = obstacleGrid[0].length;const dp = Array.from({ length: m }, () => Array(n).fill(0));// 初始化 dp 数组的第一行和第一列for (let i = 0; i < m && obstacleGrid[i][0] === 0; i++) {dp[i][0] = 1;}for (let j = 0; j < n && obstacleGrid[0][j] === 0; j++) {dp[0][j] = 1;}// 填充 dp 数组for (let i = 1; i < m; i++) {for (let j = 1; j < n; j++) {if (obstacleGrid[i][j] === 0) {dp[i][j] = dp[i - 1][j] + dp[i][j - 1];}}}return dp[m - 1][n - 1];
}

讲解
我们需要计算从起点到终点的不同路径数量,同时需要避开障碍物。基本思路是使用一个二维数组 dp 来存储从起点到每个格子的不同路径数量。为了避免障碍物,当遇到障碍物时,我们将该格子的路径数量设为 0。

  1. 初始化 dp 数组:创建一个与给定网格大小相同的二维数组 dp,并将所有值初始化为 0。
  2. 边界条件:将 dp[0][0] 设置为 1,表示起点有 1 条路径。
  3. 填充 dp 数组:从第一行和第一列开始,逐步填充 dp 数组。对于每个格子 (i, j),如果该格子不是障碍物,则 dp[i][j] 的值等于左边格子 dp[i][j-1] 和上边格子 dp[i-1][j] 的路径数量之和。
  4. 处理障碍物:如果某个格子是障碍物,则将其对应的 dp 数组中的值设为 0。
  5. 返回结果:最后,dp[m-1][n-1] 的值就是从起点到终点的不同路径数量。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/488746.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

[工具升级问题] 钉钉(linux版)升级带来的小麻烦

本文由Markdown语法编辑器编辑完成。 1. 背景: 今日钉钉又发布了新的升级版本。由于我工作时使用的是Ubuntu 20.04版本&#xff0c;收到的升级推送信息是&#xff0c;可以升级到最新的7.6.25-Release版本。根据钉钉官方给出的历次更新版说明&#xff0c;这个新的版本&#xf…

3.22SQL查询

实体完整性是数据库设计中的一个概念&#xff0c;指的是确保数据库中每个实体&#xff08;表&#xff09;在逻辑上是完整和一致的状态。它涉及到定义和强制执行一些规则和约束&#xff0c;以确保数据的完整性和准确性。 实体完整性通常通过以下方式来实现&#xff1a; 1. 主键…

y3编辑器教学5:触发器2 案例演示

文章目录 一、探索1.1 ECA1.1.1 ECA的定义1.1.2 使用触发器实现瞬间移动效果 1.2 变量1.2.1 什么是变量1.2.2 使用变量存储碎片收集数量并展现 1.3 if语句&#xff08;魔法效果挂接&#xff09;1.3.1 地形设置1.3.2 编写能量灌注逻辑1.3.3 编写能量灌注后&#xff0c;实现传送逻…

基于Qwen2-VL模型针对LaTeX OCR任务进行微调训练 - 原模型 单图推理

基于Qwen2-VL模型针对LaTeX OCR任务进行微调训练 - 原模型 单图推理 flyish 输入 输出 [‘这是一幅中国传统山水画&#xff0c;描绘了一座高耸的山峰&#xff0c;周围环绕着树木和植被。画面下方有一片开阔的田野&#xff0c;远处的山峦在薄雾中若隐若现。画面上方有几行书法…

LLM - 多模态大模型的开源评估工具 VLMEvalKit 部署与测试 教程

欢迎关注我的CSDN&#xff1a;https://spike.blog.csdn.net/ 本文地址&#xff1a;https://spike.blog.csdn.net/article/details/144353087 免责声明&#xff1a;本文来源于个人知识与公开资料&#xff0c;仅用于学术交流&#xff0c;欢迎讨论&#xff0c;不支持转载。 VLMEva…

心觉:个人成长的密码,牛顿和量子力学已给出

Hi&#xff0c;我是心觉&#xff0c;带你用潜意识化解各种焦虑、内耗&#xff0c;建立无敌自信&#xff1b;教你财富精准显化的实操方法&#xff1b;关注我,伴你一路成长&#xff01; 每日一省写作258/1000天 在探索个人成长的奥秘时&#xff0c;你可曾想过&#xff0c;那些看似…

电子商务人工智能指南 5/6 - 丰富的产品数据

介绍 81% 的零售业高管表示&#xff0c; AI 至少在其组织中发挥了中等至完全的作用。然而&#xff0c;78% 的受访零售业高管表示&#xff0c;很难跟上不断发展的 AI 格局。 近年来&#xff0c;电子商务团队加快了适应新客户偏好和创造卓越数字购物体验的需求。采用 AI 不再是一…

JS进阶DAY3|事件(三)事件委托

目录 一、事件委托 1.1 概念 1.2 代码示例 二、tab栏切换案例 一、事件委托 1.1 概念 事件委托是一种在JavaScript中常用的技术&#xff0c;它利用了DOM事件冒泡的原理。事件冒泡是指当在DOM树中较低层次的元素上发生事件时&#xff0c;这个事件会向上冒泡到更高层次的元素…

Y3编辑器文档4:触发器1(对话、装备、特效、行为树、排行榜、不同步问题)

文章目录 一、触发器简介1.1 触发器界面1.2 ECA语句编辑及快捷键1.3 参数设置1.4 变量设置1.5 实体触发器1.6 函数库与触发器复用 二、触发器的多层结构2.1 子触发器&#xff08;在游戏内对新的事件进行注册&#xff09;2.2 触发器变量作用域2.3 复合条件2.4 循环2.5 计时器2.6…

LoRA:低秩分解微调与代码

传统的微调&#xff0c;即微调全量参数&#xff0c;就是上面的公式&#xff0c;但是我们可以通过两个矩阵&#xff0c;来模拟这个全量的矩阵&#xff0c;如果原来的W是(N * N)维度&#xff0c;我们可以通过两个(N * R) 和 (R * N)的矩阵矩阵乘&#xff0c;来模拟微调的结果。 …

鸿蒙系统-前端0帧起手

鸿蒙系统-前端0帧起手 先search 一番 找到对应的入门文档1. 运行项目遇到问题 如下 &#xff08;手动设计npm 的 registry 运行 npm config set registry https://registry.npmjs.org/&#xff09;2.运行后不支持一些模拟器 配置一下&#xff08;如下图&#xff0c;运行成功&am…

Java面试之实现多线程(二)

此篇接上一篇Java面试之什么是多线程(一) Java多线程是Java语言中的一个重要特性&#xff0c;它可以实现并发处理、提高程序的性能和响应能力。开发者需要了解多线程的概念和机制&#xff0c;并采用合适的多线程编程模型和同步机制&#xff0c;以保证程序的正确性和稳定性。Jav…

酒店/电影推荐系统里面如何应用深度学习如CNN?

【1】酒店推荐系统里面如何应用CNN&#xff1f;具体过程是什么 在酒店推荐系统中应用卷积神经网络&#xff08;CNN&#xff09;并不是一个常见的选择&#xff0c;因为 CNN 主要用于处理具有空间结构的数据&#xff0c;如图像、音频和某些类型的序列数据。然而&#xff0c;在某…

三、nginx实现lnmp+discuz论坛

lnmp l&#xff1a;linux操作系统 n&#xff1a;nginx前端页面 m&#xff1a;mysql数据库&#xff0c;账号密码&#xff0c;数据库等等都保存在这个数据库里面 p&#xff1a;php——nginx擅长处理的是静态页面&#xff0c;页面登录账户&#xff0c;需要请求到数据库&#…

03篇--二值化与自适应二值化

二值化 定义 何为二值化&#xff1f;顾名思义&#xff0c;就是将图像中的像素值改为只有两种值&#xff0c;黑与白。此为二值化。 二值化操作的图像只能是灰度图&#xff0c;意思就是二值化也是一个二维数组&#xff0c;它与灰度图都属于单信道&#xff0c;仅能表示一种色调…

CV之UIGM之OmniGen:《OmniGen: Unified Image Generation》翻译与解读

CV之UIGM之OmniGen&#xff1a;《OmniGen: Unified Image Generation》翻译与解读 导读&#xff1a;这篇论文介绍了OmniGen&#xff0c;一个用于统一图像生成的扩散模型。 >> 背景痛点&#xff1a;目前的图像生成模型大多专注于特定任务&#xff0c;例如文本到图像生成。…

数据分析python小工具录入产品信息到Excel

在没有后台管理系统的时候&#xff0c;有时候为了方便起见&#xff0c;想提供一个输入框让运营人员直接输入&#xff0c;然后数据就会以数据库的形式存进数据库 效果图&#xff1a; 输入用户名 输入数据 输入信息后点击添加到表格&#xff0c;检查后方便批量保存到excel …

scala的泛型2

package test55 //隐式转换 //1.隐式函数 //2.隐式类 //3.隐式对象 //4.函数的隐式参数//泛型&#xff1a;类型参数化。 //Pair 约定一对数据 class Pair[T](var x:T, var y:T) //泛型的应用场景&#xff1a; //1.泛型函数 //2.泛型类 //3.泛型特质 object test2 {def main(arg…

【刷题22】BFS解决最短路问题

目录 一、边权为1的最短路问题二、迷宫中离入口最近的出口三、最小基因变化四、单词接龙五、为高尔夫比赛砍树 一、边权为1的最短路问题 如图&#xff1a;从A到I&#xff0c;怎样走路径最短 一个队列一个哈希表队列&#xff1a;一层一层递进&#xff0c;直到目的地为止哈希表&…

Google Cloud Database Option(数据库选项说明)

关系数据库 在关系数据库中&#xff0c;信息存储在表、行和列中&#xff0c;这通常最适合结构化数据。因此&#xff0c;它们用于数据结构不经常更改的应用程序。与大多数关系数据库交互时使用 SQL&#xff08;结构化查询语言&#xff09;。它们为数据提供 ACID 一致性模式&am…