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

leetcode-不同路径问题

一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为 “Start” )。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为 “Finish” )。

问总共有多少条不同的路径?

看见题目我们首先用动态规划四步曲进行分析。

dp数组应该怎么看?我们回想一下爬楼梯,其实本题和他也没什么区别,唯一不同的我们这个是二维的,既然要记录总共的路径那么我们就定义一个二维数组,每一个记录到该点要走多少步,和爬楼梯一样,他是只能走一步或者两步,我们是只能向下或者向右,所以我们每一点的值就等于他上面的和左边的和,毕竟他们俩是不重复的,加起来就是能到该点的所有的路径。

所以得到递推公式: dp[i][j] = dp[i-1][j]+dp[i][j-1];

那么我们怎么初始化呢,首先我们看一下递推公式,需要-1,那就意味着我们的第一行和第一列都是要初始化的,所以我们直接把他们赋值成1就可以了。

我们直接上代码

class Solution {public int uniquePaths(int m, int n) {int[][] dp = new int[m][n];for(int i = 0;i<m;i++){dp[i][0] = 1;for(int j = 0;j<n;j++){dp[0][j] = 1;}}for(int i = 1;i<m;i++){for(int j = 1;j<n;j++){dp[i][j] = dp[i-1][j]+dp[i][j-1];}}return dp[m-1][n-1];}
}  

给定一个 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. 向下 -> 向下 -> 向右 -> 向右

这一题是上一题的变种,我们的路上有障碍了,我们如何规避这个障碍呢 ,首先就是在路程中把障碍物都变成让他没办法走,一开始我就只加了这一个逻辑,但是运行起来发现不对,后来我思考了一下发现还有问题,因为我们的初始化也有问题,如果第一排就有障碍,后面的都是0啊都得不到值,所以把这俩逻辑加进来这个问题就解决啦

class Solution {public int uniquePathsWithObstacles(int[][] obstacleGrid) {int m = obstacleGrid.length;int n = obstacleGrid[0].length;if (obstacleGrid[0][0] == 1) {return 0;}// 初始化 dp 数组int[][] dp = new int[m][n];dp[0][0] = 1; // 起点路径数为 1for (int j = 1; j < n; j++) {if (obstacleGrid[0][j] == 1) {break; // 遇到障碍物,后续路径都为 0}dp[0][j] = 1;}// 初始化第一列for (int i = 1; i < m; i++) {if (obstacleGrid[i][0] == 1) {break; // 遇到障碍物,后续路径都为 0}dp[i][0] = 1;}for (int i = 1; i < m; i++) {for (int j = 1; j < n; j++) {if (obstacleGrid[i][j] == 1) {dp[i][j] = 0; // 当前格子有障碍物,路径数为 0} else {dp[i][j] = dp[i - 1][j] + dp[i][j - 1]; // 状态转移}}}return dp[m - 1][n - 1];}
}

相关文章:

leetcode-不同路径问题

一个机器人位于一个 m x n 网格的左上角 &#xff08;起始点在下图中标记为 “Start” &#xff09;。 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角&#xff08;在下图中标记为 “Finish” &#xff09;。 问总共有多少条不同的路径&#xff1f; 看见题目…...

MongoDB 数据库备份和恢复全攻略

在当今数据驱动的时代&#xff0c;数据库的稳定运行和数据安全至关重要。MongoDB 作为一款流行的 NoSQL 数据库&#xff0c;以其灵活的文档模型和高扩展性备受青睐。然而&#xff0c;无论数据库多么强大&#xff0c;数据丢失的风险始终存在&#xff0c;因此掌握 MongoDB 的备份…...

CentOS7使用源码安装PHP8教程整理

CentOS7使用源码安装PHP8教程整理 下载安装包解压下载的php tar源码包安装所需的一些依赖扩展库安装前的配置修改配置文件1、进入php8的安装包 配置环境变量开机自启启动服务创建软连接常见问题1、checking for icu-uc > 50.1 icu-io icu-i18n... no2、configure: error: Pa…...

Baklib助力内容中台实施的最佳实践与成功案例探索

内容概要 在当今数字化发展的背景下&#xff0c;内容中台的概念逐渐受到重视。内容中台不仅仅是一个技术平台&#xff0c;更是企业在内容管理和运营效率提升方面的重要助力。它通过整合内部资源&#xff0c;实现信息的集中管理与高效利用&#xff0c;帮助企业应对日益复杂的市…...

rocketmq-product-send方法源码分析

先看有哪些send方法 首先说红圈的 有3个红圈。归类成3种发送方式。假设前提条件&#xff0c;发送的topic&#xff0c;有3个broker&#xff0c;每个broker总共4个write队列&#xff0c;总共有12个队列。 普通发送。负载均衡12个队列。指定超时时间指定MessageQueue,发送&#…...

python flask中使用or查询和and查询,还有同时使用or、and的情况

在 Flask 中处理数据库查询时&#xff0c;通常会结合使用 ORM 工具&#xff0c;例如 SQLAlchemy。以下是 or 查询、and 查询以及两者同时使用的示例。 文章目录 基础准备1. 使用 or_ 查询2. 使用 and_ 查询3. 同时使用 or_ 和 and_4. 更加复杂的嵌套查询 基础准备 假设有一个…...

【第一天】零基础入门刷题Python-算法篇-数据结构与算法的介绍(持续更新)

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 文章目录 前言一、Python数据结构与算法的详细介绍1.基本概念2.Python中的数据结构1. 列表&#xff08;List&#xff09;2. 元组&#xff08;Tuple&#xff09;3. 字典&#…...

租房管理系统实现智能化租赁提升用户体验与运营效率

内容概要 在当今快速发展的租赁市场中&#xff0c;租房管理系统的智能化转型显得尤为重要。它不仅帮助房东和租客之间建立更高效的沟通桥梁&#xff0c;还优化了整个租赁流程。通过智能化技术&#xff0c;这套系统能够自动处理资产管理、合同签署、财务管理等所有关键环节。这…...

python3+TensorFlow 2.x(四)反向传播

目录 反向传播算法 反向传播算法基本步骤&#xff1a; 反向中的参数变化 总结 反向传播算法 反向传播算法&#xff08;Backpropagation&#xff09;是训练人工神经网络时使用的一个重要算法&#xff0c;它是通过计算梯度并优化神经网络的权重来最小化误差。反向传播算法的核…...

Flutter 使用 flutter_inappwebview 加载 App 本地 HTML 文件

在 Flutter 开发中&#xff0c;加载本地 HTML 文件是一个常见的需求&#xff0c;尤其是在需要展示离线内容或自定义页面时。flutter_inappwebview 是一个功能强大的插件&#xff0c;支持加载本地文件和网络资源。本文将详细介绍如何使用 flutter_inappwebview 加载 App 本地 HT…...

Word常见问题:嵌入图片无法显示完整

场景&#xff1a;在Word中&#xff0c;嵌入式图片显示不全&#xff0c;一部分图片在文字下方。如&#xff1a; 问题原因&#xff1a;因段落行距导致 方法一 快捷方式 选中图片&#xff0c;通过"ctrl1"快捷调整为1倍行距 方法二 通过工具栏调整 选中图片&#xff0…...

为AI聊天工具添加一个知识系统 之68 详细设计 之9 三种中台和时间度量 之1

本文要点 要点 在维度0上 被分离出来 的业务中台 需求、技术中台要求、和数据中台请求 &#xff08;分别在时间层/空间层/时空层上 对应一个不同种类槽的容器&#xff0c;分别表示业务特征Feature[3]/技术方面Aspect[3]/数据流Fluent[3]&#xff09; 在维度1~3的运动过程中 从…...

On to OpenGL and 3D computer graphics

2. On to OpenGL and 3D computer graphics 声明&#xff1a;该代码来自&#xff1a;Computer Graphics Through OpenGL From Theory to Experiments&#xff0c;仅用作学习参考 2.1 First Program Square.cpp完整代码 /// // square.cpp // // OpenGL program to draw a squ…...

从曾国藩的经历看如何打破成长中的瓶颈

《曾国藩传》是一部充满智慧与人生哲理的传记&#xff0c;而曾国藩本人更是一个从“最笨”到“最智慧”的奇人。看他的成长与蜕变&#xff0c;不仅能感受到他如何超越自己的局限&#xff0c;也能从中获得关于人性、社会和历史的重要启示。曾国藩的一生让人深思&#xff0c;正是…...

JavaWeb学习-SpringBotWeb开发入门(HTTP协议)

(一)SpringBotWeb开发步骤 (1)创建springboot工程,并勾选开发相关依赖 (2)定义HelloController类,添加方法hello,并添加注解 (3)运行测试 (二)HTTP入门概述 创建请求页面 package com.itheima.demo3; /*请求处理类,加上注解标识为请求处理类*/import org.spr…...

数据库用户管理

数据库用户管理 1.创建用户 MySQL在安装是&#xff0c;会默认创建一个名位root的用户&#xff0c;该用户拥有超级权限&#xff0c;可以控制整个MySQL服务器。 在对MySQL的日常管理和操作中&#xff0c;通常创建一些具有适当权限的用户&#xff0c;尽可能的不用或少用root登录…...

BGP边界网关协议(Border Gateway Protocol)路由聚合详解

一、路由聚合 1、意义 在大规模的网络中&#xff0c;BGP路由表十分庞大&#xff0c;给设备造成了很大的负担&#xff0c;同时使发生路由振荡的几率也大大增加&#xff0c;影响网络的稳定性。 路由聚合是将多条路由合并的机制&#xff0c;它通过只向对等体发送聚合后的路由而…...

ASP.NET Core WebAPI的异步及返回值

目录 Action方法的异步 Action方法参数 捕捉URL占位符 捕捉QueryString的值 JSON报文体 其他方式 Action方法的异步 Action方法既可以同步也可以异步。异步Action方法的名字一般不需要以Async结尾。Web API中Action方法的返回值如果是普通数据类型&#xff0c;那么返回值…...

「 机器人 」仿生扑翼飞行器中的“被动旋转机制”概述

前言 在仿生扑翼飞行器的机翼设计中,模仿昆虫翼的被动旋转机制是一项关键技术。其核心思想在于:机翼旋转角度(攻角)并非完全通过主动伺服来控制,而是利用空气动力和惯性力的作用,自然地实现被动调节。以下对这种设计的背景、原理与优势进行详细说明。 1. 背景:昆虫的被动…...

「 机器人 」扑翼飞行器的数据驱动建模核心方法

前言 数据驱动建模可充分利用扑翼飞行器的已有运行数据,改进动力学模型与控制策略,并对未建模动态做出更精确的预测。在复杂的非线性飞行环境中,该方法能有效弥补传统解析建模的不足,具有较高的研究与应用价值。以下针对主要研究方向和实现步骤进行整理与阐述。 1. 数据驱动…...

基于大模型的 UI 自动化系统

基于大模型的 UI 自动化系统 下面是一个完整的 Python 系统,利用大模型实现智能 UI 自动化,结合计算机视觉和自然语言处理技术,实现"看屏操作"的能力。 系统架构设计 #mermaid-svg-2gn2GRvh5WCP2ktF {font-family:"trebuchet ms",verdana,arial,sans-…...

脑机新手指南(八):OpenBCI_GUI:从环境搭建到数据可视化(下)

一、数据处理与分析实战 &#xff08;一&#xff09;实时滤波与参数调整 基础滤波操作 60Hz 工频滤波&#xff1a;勾选界面右侧 “60Hz” 复选框&#xff0c;可有效抑制电网干扰&#xff08;适用于北美地区&#xff0c;欧洲用户可调整为 50Hz&#xff09;。 平滑处理&…...

如何将联系人从 iPhone 转移到 Android

从 iPhone 换到 Android 手机时&#xff0c;你可能需要保留重要的数据&#xff0c;例如通讯录。好在&#xff0c;将通讯录从 iPhone 转移到 Android 手机非常简单&#xff0c;你可以从本文中学习 6 种可靠的方法&#xff0c;确保随时保持连接&#xff0c;不错过任何信息。 第 1…...

pikachu靶场通关笔记19 SQL注入02-字符型注入(GET)

目录 一、SQL注入 二、字符型SQL注入 三、字符型注入与数字型注入 四、源码分析 五、渗透实战 1、渗透准备 2、SQL注入探测 &#xff08;1&#xff09;输入单引号 &#xff08;2&#xff09;万能注入语句 3、获取回显列orderby 4、获取数据库名database 5、获取表名…...

9-Oracle 23 ai Vector Search 特性 知识准备

很多小伙伴是不是参加了 免费认证课程&#xff08;限时至2025/5/15&#xff09; Oracle AI Vector Search 1Z0-184-25考试&#xff0c;都顺利拿到certified了没。 各行各业的AI 大模型的到来&#xff0c;传统的数据库中的SQL还能不能打&#xff0c;结构化和非结构的话数据如何和…...

pycharm 设置环境出错

pycharm 设置环境出错 pycharm 新建项目&#xff0c;设置虚拟环境&#xff0c;出错 pycharm 出错 Cannot open Local Failed to start [powershell.exe, -NoExit, -ExecutionPolicy, Bypass, -File, C:\Program Files\JetBrains\PyCharm 2024.1.3\plugins\terminal\shell-int…...

​​企业大模型服务合规指南:深度解析备案与登记制度​​

伴随AI技术的爆炸式发展&#xff0c;尤其是大模型&#xff08;LLM&#xff09;在各行各业的深度应用和整合&#xff0c;企业利用AI技术提升效率、创新服务的步伐不断加快。无论是像DeepSeek这样的前沿技术提供者&#xff0c;还是积极拥抱AI转型的传统企业&#xff0c;在面向公众…...

门静脉高压——表现

一、门静脉高压表现 00:01 1. 门静脉构成 00:13 组成结构&#xff1a;由肠系膜上静脉和脾静脉汇合构成&#xff0c;是肝脏血液供应的主要来源。淤血后果&#xff1a;门静脉淤血会同时导致脾静脉和肠系膜上静脉淤血&#xff0c;引发后续系列症状。 2. 脾大和脾功能亢进 00:46 …...

2025.6.9总结(利与弊)

凡事都有两面性。在大厂上班也不例外。今天找开发定位问题&#xff0c;从一个接口人不断溯源到另一个 接口人。有时候&#xff0c;不知道是谁的责任填。将工作内容分的很细&#xff0c;每个人负责其中的一小块。我清楚的意识到&#xff0c;自己就是个可以随时替换的螺丝钉&…...

EEG-fNIRS联合成像在跨频率耦合研究中的创新应用

摘要 神经影像技术对医学科学产生了深远的影响&#xff0c;推动了许多神经系统疾病研究的进展并改善了其诊断方法。在此背景下&#xff0c;基于神经血管耦合现象的多模态神经影像方法&#xff0c;通过融合各自优势来提供有关大脑皮层神经活动的互补信息。在这里&#xff0c;本研…...