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 网格的左上角 (起始点在下图中标记为 “Start” )。 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为 “Finish” )。 问总共有多少条不同的路径? 看见题目…...
MongoDB 数据库备份和恢复全攻略
在当今数据驱动的时代,数据库的稳定运行和数据安全至关重要。MongoDB 作为一款流行的 NoSQL 数据库,以其灵活的文档模型和高扩展性备受青睐。然而,无论数据库多么强大,数据丢失的风险始终存在,因此掌握 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助力内容中台实施的最佳实践与成功案例探索
内容概要 在当今数字化发展的背景下,内容中台的概念逐渐受到重视。内容中台不仅仅是一个技术平台,更是企业在内容管理和运营效率提升方面的重要助力。它通过整合内部资源,实现信息的集中管理与高效利用,帮助企业应对日益复杂的市…...

rocketmq-product-send方法源码分析
先看有哪些send方法 首先说红圈的 有3个红圈。归类成3种发送方式。假设前提条件,发送的topic,有3个broker,每个broker总共4个write队列,总共有12个队列。 普通发送。负载均衡12个队列。指定超时时间指定MessageQueue,发送&#…...
python flask中使用or查询和and查询,还有同时使用or、and的情况
在 Flask 中处理数据库查询时,通常会结合使用 ORM 工具,例如 SQLAlchemy。以下是 or 查询、and 查询以及两者同时使用的示例。 文章目录 基础准备1. 使用 or_ 查询2. 使用 and_ 查询3. 同时使用 or_ 和 and_4. 更加复杂的嵌套查询 基础准备 假设有一个…...
【第一天】零基础入门刷题Python-算法篇-数据结构与算法的介绍(持续更新)
提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档 文章目录 前言一、Python数据结构与算法的详细介绍1.基本概念2.Python中的数据结构1. 列表(List)2. 元组(Tuple)3. 字典&#…...

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

python3+TensorFlow 2.x(四)反向传播
目录 反向传播算法 反向传播算法基本步骤: 反向中的参数变化 总结 反向传播算法 反向传播算法(Backpropagation)是训练人工神经网络时使用的一个重要算法,它是通过计算梯度并优化神经网络的权重来最小化误差。反向传播算法的核…...
Flutter 使用 flutter_inappwebview 加载 App 本地 HTML 文件
在 Flutter 开发中,加载本地 HTML 文件是一个常见的需求,尤其是在需要展示离线内容或自定义页面时。flutter_inappwebview 是一个功能强大的插件,支持加载本地文件和网络资源。本文将详细介绍如何使用 flutter_inappwebview 加载 App 本地 HT…...

Word常见问题:嵌入图片无法显示完整
场景:在Word中,嵌入式图片显示不全,一部分图片在文字下方。如: 问题原因:因段落行距导致 方法一 快捷方式 选中图片,通过"ctrl1"快捷调整为1倍行距 方法二 通过工具栏调整 选中图片࿰…...
为AI聊天工具添加一个知识系统 之68 详细设计 之9 三种中台和时间度量 之1
本文要点 要点 在维度0上 被分离出来 的业务中台 需求、技术中台要求、和数据中台请求 (分别在时间层/空间层/时空层上 对应一个不同种类槽的容器,分别表示业务特征Feature[3]/技术方面Aspect[3]/数据流Fluent[3]) 在维度1~3的运动过程中 从…...

On to OpenGL and 3D computer graphics
2. On to OpenGL and 3D computer graphics 声明:该代码来自:Computer Graphics Through OpenGL From Theory to Experiments,仅用作学习参考 2.1 First Program Square.cpp完整代码 /// // square.cpp // // OpenGL program to draw a squ…...
从曾国藩的经历看如何打破成长中的瓶颈
《曾国藩传》是一部充满智慧与人生哲理的传记,而曾国藩本人更是一个从“最笨”到“最智慧”的奇人。看他的成长与蜕变,不仅能感受到他如何超越自己的局限,也能从中获得关于人性、社会和历史的重要启示。曾国藩的一生让人深思,正是…...
JavaWeb学习-SpringBotWeb开发入门(HTTP协议)
(一)SpringBotWeb开发步骤 (1)创建springboot工程,并勾选开发相关依赖 (2)定义HelloController类,添加方法hello,并添加注解 (3)运行测试 (二)HTTP入门概述 创建请求页面 package com.itheima.demo3; /*请求处理类,加上注解标识为请求处理类*/import org.spr…...
数据库用户管理
数据库用户管理 1.创建用户 MySQL在安装是,会默认创建一个名位root的用户,该用户拥有超级权限,可以控制整个MySQL服务器。 在对MySQL的日常管理和操作中,通常创建一些具有适当权限的用户,尽可能的不用或少用root登录…...

BGP边界网关协议(Border Gateway Protocol)路由聚合详解
一、路由聚合 1、意义 在大规模的网络中,BGP路由表十分庞大,给设备造成了很大的负担,同时使发生路由振荡的几率也大大增加,影响网络的稳定性。 路由聚合是将多条路由合并的机制,它通过只向对等体发送聚合后的路由而…...
ASP.NET Core WebAPI的异步及返回值
目录 Action方法的异步 Action方法参数 捕捉URL占位符 捕捉QueryString的值 JSON报文体 其他方式 Action方法的异步 Action方法既可以同步也可以异步。异步Action方法的名字一般不需要以Async结尾。Web API中Action方法的返回值如果是普通数据类型,那么返回值…...

「 机器人 」仿生扑翼飞行器中的“被动旋转机制”概述
前言 在仿生扑翼飞行器的机翼设计中,模仿昆虫翼的被动旋转机制是一项关键技术。其核心思想在于:机翼旋转角度(攻角)并非完全通过主动伺服来控制,而是利用空气动力和惯性力的作用,自然地实现被动调节。以下对这种设计的背景、原理与优势进行详细说明。 1. 背景:昆虫的被动…...
「 机器人 」扑翼飞行器的数据驱动建模核心方法
前言 数据驱动建模可充分利用扑翼飞行器的已有运行数据,改进动力学模型与控制策略,并对未建模动态做出更精确的预测。在复杂的非线性飞行环境中,该方法能有效弥补传统解析建模的不足,具有较高的研究与应用价值。以下针对主要研究方向和实现步骤进行整理与阐述。 1. 数据驱动…...

【大模型RAG】拍照搜题技术架构速览:三层管道、两级检索、兜底大模型
摘要 拍照搜题系统采用“三层管道(多模态 OCR → 语义检索 → 答案渲染)、两级检索(倒排 BM25 向量 HNSW)并以大语言模型兜底”的整体框架: 多模态 OCR 层 将题目图片经过超分、去噪、倾斜校正后,分别用…...

深入剖析AI大模型:大模型时代的 Prompt 工程全解析
今天聊的内容,我认为是AI开发里面非常重要的内容。它在AI开发里无处不在,当你对 AI 助手说 "用李白的风格写一首关于人工智能的诗",或者让翻译模型 "将这段合同翻译成商务日语" 时,输入的这句话就是 Prompt。…...
Golang dig框架与GraphQL的完美结合
将 Go 的 Dig 依赖注入框架与 GraphQL 结合使用,可以显著提升应用程序的可维护性、可测试性以及灵活性。 Dig 是一个强大的依赖注入容器,能够帮助开发者更好地管理复杂的依赖关系,而 GraphQL 则是一种用于 API 的查询语言,能够提…...
将对透视变换后的图像使用Otsu进行阈值化,来分离黑色和白色像素。这句话中的Otsu是什么意思?
Otsu 是一种自动阈值化方法,用于将图像分割为前景和背景。它通过最小化图像的类内方差或等价地最大化类间方差来选择最佳阈值。这种方法特别适用于图像的二值化处理,能够自动确定一个阈值,将图像中的像素分为黑色和白色两类。 Otsu 方法的原…...

关键领域软件测试的突围之路:如何破解安全与效率的平衡难题
在数字化浪潮席卷全球的今天,软件系统已成为国家关键领域的核心战斗力。不同于普通商业软件,这些承载着国家安全使命的软件系统面临着前所未有的质量挑战——如何在确保绝对安全的前提下,实现高效测试与快速迭代?这一命题正考验着…...
scikit-learn机器学习
# 同时添加如下代码, 这样每次环境(kernel)启动的时候只要运行下方代码即可: # Also add the following code, # so that every time the environment (kernel) starts, # just run the following code: import sys sys.path.append(/home/aistudio/external-libraries)机…...

Ubuntu Cursor升级成v1.0
0. 当前版本低 使用当前 Cursor v0.50时 GitHub Copilot Chat 打不开,快捷键也不好用,当看到 Cursor 升级后,还是蛮高兴的 1. 下载 Cursor 下载地址:https://www.cursor.com/cn/downloads 点击下载 Linux (x64) ,…...

ubuntu系统文件误删(/lib/x86_64-linux-gnu/libc.so.6)修复方案 [成功解决]
报错信息:libc.so.6: cannot open shared object file: No such file or directory: #ls, ln, sudo...命令都不能用 error while loading shared libraries: libc.so.6: cannot open shared object file: No such file or directory重启后报错信息&…...
书籍“之“字形打印矩阵(8)0609
题目 给定一个矩阵matrix,按照"之"字形的方式打印这个矩阵,例如: 1 2 3 4 5 6 7 8 9 10 11 12 ”之“字形打印的结果为:1,…...
node.js的初步学习
那什么是node.js呢? 和JavaScript又是什么关系呢? node.js 提供了 JavaScript的运行环境。当JavaScript作为后端开发语言来说, 需要在node.js的环境上进行当JavaScript作为前端开发语言来说,需要在浏览器的环境上进行 Node.js 可…...