算法29:不同路径问题(力扣62和63题)--针对算法28进行扩展
题目:力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台
一个机器人位于一个 m x n
网格的左上角 (起始点在下图中标记为 “Start” )。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为 “Finish” )。
问总共有多少条不同的路径?
分析:
假设为3行2列的二维数组
1. 向右---向下---向下
2. 向下---向下---向右
3. 向下--向右---向下
可以推导
1. 一直向右和一直向下,每种走法只有1种走法,没有其他可以旋转的空间。因此
1 | 1 |
1 | 2 |
1 |
2 、那么到达dp[1][1] 的走法就是 1 + 1 = 2;
3. 那么到达右下角dp[2][1] 就是 2 + 1 = 3; 即3种走法
分析2:
假设有3行7列
1. 按行走,只有1种走法
2、按列走,只有一种走法,可得
1 | 1 | 1 | 1 | 1 | 1 | 1 |
1 | ||||||
1 |
那么dp[1][1] 就是 dp[0][1] + dp[1][0] 即 1+ 1 = 2;依次类推可得
1 | 1 | 1 | 1 | 1 | 1 | 1 |
1 | 2 | 3 | 4 | 5 | 6 | 7 |
1 |
第三行还是按照这种方式推导,可得
1 | 1 | 1 | 1 | 1 | 1 | 1 |
1 | 2 | 3 | 4 | 5 | 6 | 7 |
1 | 3 | 6 | 10 | 15 | 21 | 28 |
因此,针对3行7列的二维数组,可得28种走法
代码实现:
public int uniquePaths(int m, int n) {int[][] dp = new int[m][n];//第一行都为1for (int col = 0; col < n; col++) {dp[0][col] = 1;}//第一列都为1for (int row = 0; row < m; row++) {dp[row][0] = 1;}for (int row = 1; row < m; row++) {for(int col = 1; col < n; col++) {dp[row][col] = dp[row][col - 1] + dp[row - 1][col];}}return dp[m-1][n-1];}
还是一样的问题,以上代码的时间复杂度为O(m*n), 空间复杂度也为O(m*n). 如果100行100列的二维数组,将浪费100*100的空间复杂度。
空间压缩进行优化:
public int uniquePaths2(int m, int n) {int[] dp = new int[n];//第一行都为1for (int col = 0; col < n; col++) {dp[col] = 1;}for (int row = 1; row < m; row++) {dp[0] = 1;for (int col = 1; col < n; col++) {dp[col] = dp[col -1] + dp[col];}}return dp[n -1];}
完整代码:
package code03.动态规划_07.lesson4;//力扣62题
// https://leetcode.cn/problems/unique-paths/description/
public class DiffPathSum_02 {public int uniquePaths(int m, int n) {int[][] dp = new int[m][n];//第一行都为1for (int col = 0; col < n; col++) {dp[0][col] = 1;}//第一列都为1for (int row = 0; row < m; row++) {dp[row][0] = 1;}for (int row = 1; row < m; row++) {for(int col = 1; col < n; col++) {dp[row][col] = dp[row][col - 1] + dp[row - 1][col];}}return dp[m-1][n-1];}public int uniquePaths2(int m, int n) {int[] dp = new int[n];//第一行都为1for (int col = 0; col < n; col++) {dp[col] = 1;}for (int row = 1; row < m; row++) {dp[0] = 1;for (int col = 1; col < n; col++) {dp[col] = dp[col -1] + dp[col];}}return dp[n -1];}
}
力扣测试通过:
题目:力扣63题: 力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台
一个机器人位于一个 m x n
网格的左上角 (起始点在下图中标记为 “Start” )。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为 “Finish”)。
现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径?
网格中的障碍物和空位置分别用 1
和 0
来表示。
分析:
1. 这一题其实跟上面一体解法相同,唯一的不同之处是有障碍物。
2. 第一行和第一列遇到障碍物,那么后面的路都走不通而已
3. 后面的推导,当前方格为障碍物,设置0代表走不通;如果不为0,则按照原有逻辑进行推导即可
完整代码:
package code03.动态规划_07.lesson4;//力扣63题
// https://leetcode.cn/problems/unique-paths-ii/description/
public class DiffPathSum_03 {//时间复杂度 O(m*n), 空间复杂度 O(m*n)public int uniquePathsWithObstacles(int[][] obstacleGrid) {int m = obstacleGrid.length;int n = obstacleGrid[0].length;//obstacleGrid[0][0] == 1 代表左上角第一个就是障碍物//obstacleGrid[m-1][n-1] == 1 代表右下角最后一个是障碍物if (obstacleGrid == null|| obstacleGrid.length == 0|| obstacleGrid[0][0] == 1|| obstacleGrid[m-1][n-1] == 1) {return 0;}int[][] dp = new int[m][n];//处理第一行dp[0][0] = 1;for (int col = 1; col < n; col++) {//如果当前列为1, 或者前一列为0. 代表遇到障碍物。后面路走不通,全部变为0if (obstacleGrid[0][col] == 1 || dp[0][col -1] == 0) {dp[0][col] = 0;} else {//第一行只有1条路dp[0][col] = 1;}}//处理第一列for (int row = 1; row < m; row++) {//如果当前列为1, 或者上一列为0. 代表遇到障碍物。后面路走不通,全部变为0if (obstacleGrid[row][0] == 1 || dp[row-1][0] == 0) {dp[row][0] = 0;} else {//第一行只有1条路dp[row][0] = 1;}}for (int row = 1; row < m; row++) {for(int col = 1; col < n; col++) {//如果当前列有障碍物,此条路走不通。当前列的值变为0//否则,按照原有的逻辑进行计算dp[row][col] = obstacleGrid[row][col] == 1 ? 0: dp[row][col - 1] + dp[row - 1][col];}}return dp[m-1][n-1];}//空间压缩//时间复杂度 O(m*n), 空间复杂度 O(n)public int uniquePathsWithObstacles2(int[][] obstacleGrid) {int m = obstacleGrid.length;int n = obstacleGrid[0].length;//obstacleGrid[0][0] == 1 代表左上角第一个就是障碍物//obstacleGrid[m-1][n-1] == 1 代表右下角最后一个是障碍物if (obstacleGrid == null|| obstacleGrid.length == 0|| obstacleGrid[0][0] == 1|| obstacleGrid[m-1][n-1] == 1) {return 0;}int[] dp = new int[n];//处理第一行dp[0] = 1;for (int col = 1; col < n; col++) {//如果当前列为1, 或者前一列为0. 代表遇到障碍物。后面路走不通,全部变为0if (obstacleGrid[0][col] == 1 || dp[col -1] == 0) {dp[col] = 0;} else {//第一行只有1条路dp[col] = 1;}}for (int row = 1; row < m; row++) {//当前列为障碍物或者上一列为障碍物,都走不通。dp[0] = (obstacleGrid[row][0] == 1 || dp[0] == 0) ? 0 : 1;for(int col = 1; col < n; col++) {//如果当前列有障碍物,此条路走不通。当前列的值变为0//否则,按照原有的逻辑进行计算dp[col] = obstacleGrid[row][col] == 1 ? 0 : dp[col -1] + dp[col];}}return dp[n-1];}public static void main(String[] args) {DiffPathSum_03 test = new DiffPathSum_03();int[][] arr = {{0, 0, 0},{0, 1, 0},{0, 0, 0}};System.out.println(test.uniquePathsWithObstacles2(arr));}
}
相关文章:

算法29:不同路径问题(力扣62和63题)--针对算法28进行扩展
题目:力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台 一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为 “Start” )。 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角࿰…...

openGauss学习笔记-188 openGauss 数据库运维-常见故障定位案例-core问题定位
文章目录 openGauss学习笔记-188 openGauss 数据库运维-常见故障定位案例-core问题定位188.1 磁盘满故障引起的core问题188.1.1 问题现象188.1.2 原因分析188.1.3 处理办法 188.2 GUC参数log_directory设置不正确引起的core问题188.2.1 问题现象188.2.2 原因分析188.2.3 处理办…...

kubernetes入门到进阶(5)
目录 镜像仓库:怎么用好docker hub这个宝藏 什么是镜像仓库(Registry) 什么是docker hub 如何在docker hub上挑选镜像 docker hub上进行概念股命名规则是什么 该怎么上传自己的镜像 离线环境该怎么办 小结 镜像仓库:怎么用好docke…...

【字典树Trie】LeetCode-139. 单词拆分
139. 单词拆分。 给你一个字符串 s 和一个字符串列表 wordDict 作为字典。请你判断是否可以利用字典中出现的单词拼接出 s 。 注意:不要求字典中出现的单词全部都使用,并且字典中的单词可以重复使用。 示例 1: 输入: s "leetcode&q…...
pytest常用的第三方插件介绍
本节介绍了如何安装和使用第三方插件。如果你想要编写自己的插件,请参阅“编写插件”。 通过pip可以轻松安装第三方插件: pip install pytest-NAME pip uninstall pytest-NAME如果已经安装了插件,pytest会自动找到并集成它,无需手…...

【经验】VSCode连接远程服务器(可以使用git管理、方便查看和编辑Linux源码)
1、查看OpenSSH Windows10通常自带OpenSSH不需要安装。 Windows10下检查是否已经安装OpenSSH的方法: 1)按下快捷键Win + X,选择Windows PoweShell(管理员) 2)输入以下指令: Get-WindowsCapability -Online | ? Name -like ‘OpenSSH*’ 3)如果电脑未安装OpenSSH,…...

机器学习-生存分析:如何基于随机生存森林训练乳腺癌风险评估模型?
一、 引言 乳腺癌是女性最常见的恶性肿瘤之一,也是全球范围内女性死亡率最高的癌症之一。据统计,每年全球有超过200万人被诊断为乳腺癌,其中约60万人死于该疾病。因此,乳腺癌的早期诊断和风险评估对于预防和治疗乳腺癌具有非常重要…...
MySQL学习笔记1: 数据库的简单介绍
目录 1. 数据库是什么2. 数据库这一类软件中的一些典型代表2.1. Oracle2.2. MySQL2.3. SQL Server2.4. SQLite (lite 轻量版) 3. 数据库的类型3.1. 关系型数据库3.2. 非关系型数据库 4. 总结 1. 数据库是什么 数据库是一类软件,这一类软件可以用来管理数据…...
【Docker】安装ELK(Docker Compose)
一、创建挂载目录 mkdir -p /docker/elk/elasticsearch/{plugins,data} mkdir -p /docker/elk/logstash 二、给目录授权 chmod 777 /docker/elk/elasticsearch/data 创建logstash配置文件 vim /docker/elk/logstash/logstash.conf input {tcp {mode => "server" h…...

【机器学习:欧氏距离 】机器学习中欧氏距离的理解和应用
【机器学习:欧氏距离 】机器学习中欧氏距离的理解和应用 距离公式二维更高的维度点以外的物体属性欧几里得距离的平方概括历史 在数学中,欧氏距离’是指欧氏空间中任意两点之间的直线距离。这种距离可以通过应用勾股定理来计算,利用两点的笛卡…...

系统安全及应用
1、基本安全措施 1.1、系统账号清理 在Linux系统中,除了用户手动创建的各种账号之外,还包括随系统或程序安装过程而生产的其他大量账号。除了超级用户root之外,其他大量账号只是用来维护系统运作、启动或保持服务进程,一般是不允…...

Danil Pristupov Fork(强大而易用的Git客户端) for Mac/Windows
在当今软件开发领域,团队协作和版本控制是非常重要的方面。在这个过程中,Git成为了最受欢迎的版本控制工具之一。然而,对于Git的使用,一个好的客户端是至关重要的。 今天,我们要为大家介绍一款强大而易用的Git客户端—…...

最新GPT4.0使用教程,AI绘画,ChatFile文档对话总结+GPT语音对话使用,DALL-E3文生图
一、前言 ChatGPT3.5、GPT4.0、GPT语音对话、Midjourney绘画,文档对话总结DALL-E3文生图,相信对大家应该不感到陌生吧?简单来说,GPT-4技术比之前的GPT-3.5相对来说更加智能,会根据用户的要求生成多种内容甚至也可以和…...

【ARM 嵌入式 编译系列 7.2 -- GCC 链接脚本中 DEFINED 函数与 “AT>“ 符号详细介绍】
文章目录 GCC 链接脚本中 DEFINED 函数DEFINED() 函数> (放置在哪个区域)AT> (加载地址) (填充字节) 在链接脚本中,组合示例 GCC 链接脚本中 DEFINED 函数 在 ARM GCC 链接脚本(.ld 文件)中,DEFINED() 是一种内置函数&…...

Linux基础——进程初识(二)
1. 对当前目录创建文件的理解 我们知道在创建一个文件时,它会被默认创建到当前目录下,那么它是如何知道当前目录的呢? 对于下面这样一段代码 #include <stdio.h> #include <unistd.h>int main() {fopen("tmp.txt", …...

国科大图像处理2024速通期末——汇总2017-2019、2023回忆
国科大2023.12.28图像处理0854期末重点 图像处理 王伟强 作业 课件 资料 一、填空 一个阴极射线管它的输入与输出满足 s r 2 sr^{2} sr2,这将使得显示系统产生比希望的效果更暗的图像,此时伽马校正通常在信号进入显示器前被进行预处理,令p…...
编程笔记 html5cssjs 026 HTML输入类型(2/2)
编程笔记 html5&css&js 026 HTML输入类型(2/2) 输入类型:date输入类型:color输入类型:range输入类型:month输入类型:week输入类型:time输入类型:datetime输入类型…...

Vue2 - 数据响应式原理
目录 1,总览2,Observer3,Dep4,Watcher5,Schedule 1,总览 vue2官网参考 简单介绍下上图流程:以 Data 为中心来说, Vue 会将传递给 Vue 实例的 data 选项(普通 js 对象&a…...

基于华为云解析服务实现网站区域封禁
前言 中国大陆以外的网络攻击不断,个人博客时常遭受不明个人或组织的攻击,给网站的安全运行带来了巨大的风险,同时DDoS、CC攻击等还会消耗服务器的资源,站长可能需要因此支付高昂的服务器、CDN的流量费用。 因此,如果…...
在 Docker 中配置 MySQL 数据库并初始化 Project 项目
1. 文件准备 1.1. 添加 SQL 文件头部内容 每个 SQL 文件的头部需要添加以下内容: DROP DATABASE IF EXISTS xx_..; CREATE DATABASE xx_..; USE xx_..;1.2. 修改 AUTO_INCREMENT 在每个 SQL 文件中,将 AUTO_INCREMENT 修改为 1。 1.3. 插入机型 在 SQL…...
设计模式和设计原则回顾
设计模式和设计原则回顾 23种设计模式是设计原则的完美体现,设计原则设计原则是设计模式的理论基石, 设计模式 在经典的设计模式分类中(如《设计模式:可复用面向对象软件的基础》一书中),总共有23种设计模式,分为三大类: 一、创建型模式(5种) 1. 单例模式(Sing…...

React第五十七节 Router中RouterProvider使用详解及注意事项
前言 在 React Router v6.4 中,RouterProvider 是一个核心组件,用于提供基于数据路由(data routers)的新型路由方案。 它替代了传统的 <BrowserRouter>,支持更强大的数据加载和操作功能(如 loader 和…...

以下是对华为 HarmonyOS NETX 5属性动画(ArkTS)文档的结构化整理,通过层级标题、表格和代码块提升可读性:
一、属性动画概述NETX 作用:实现组件通用属性的渐变过渡效果,提升用户体验。支持属性:width、height、backgroundColor、opacity、scale、rotate、translate等。注意事项: 布局类属性(如宽高)变化时&#…...

汽车生产虚拟实训中的技能提升与生产优化
在制造业蓬勃发展的大背景下,虚拟教学实训宛如一颗璀璨的新星,正发挥着不可或缺且日益凸显的关键作用,源源不断地为企业的稳健前行与创新发展注入磅礴强大的动力。就以汽车制造企业这一极具代表性的行业主体为例,汽车生产线上各类…...

2.Vue编写一个app
1.src中重要的组成 1.1main.ts // 引入createApp用于创建应用 import { createApp } from "vue"; // 引用App根组件 import App from ./App.vue;createApp(App).mount(#app)1.2 App.vue 其中要写三种标签 <template> <!--html--> </template>…...

Vue2 第一节_Vue2上手_插值表达式{{}}_访问数据和修改数据_Vue开发者工具
文章目录 1.Vue2上手-如何创建一个Vue实例,进行初始化渲染2. 插值表达式{{}}3. 访问数据和修改数据4. vue响应式5. Vue开发者工具--方便调试 1.Vue2上手-如何创建一个Vue实例,进行初始化渲染 准备容器引包创建Vue实例 new Vue()指定配置项 ->渲染数据 准备一个容器,例如: …...

【论文阅读28】-CNN-BiLSTM-Attention-(2024)
本文把滑坡位移序列拆开、筛优质因子,再用 CNN-BiLSTM-Attention 来动态预测每个子序列,最后重构出总位移,预测效果超越传统模型。 文章目录 1 引言2 方法2.1 位移时间序列加性模型2.2 变分模态分解 (VMD) 具体步骤2.3.1 样本熵(S…...
AspectJ 在 Android 中的完整使用指南
一、环境配置(Gradle 7.0 适配) 1. 项目级 build.gradle // 注意:沪江插件已停更,推荐官方兼容方案 buildscript {dependencies {classpath org.aspectj:aspectjtools:1.9.9.1 // AspectJ 工具} } 2. 模块级 build.gradle plu…...

人工智能(大型语言模型 LLMs)对不同学科的影响以及由此产生的新学习方式
今天是关于AI如何在教学中增强学生的学习体验,我把重要信息标红了。人文学科的价值被低估了 ⬇️ 转型与必要性 人工智能正在深刻地改变教育,这并非炒作,而是已经发生的巨大变革。教育机构和教育者不能忽视它,试图简单地禁止学生使…...

push [特殊字符] present
push 🆚 present 前言present和dismiss特点代码演示 push和pop特点代码演示 前言 在 iOS 开发中,push 和 present 是两种不同的视图控制器切换方式,它们有着显著的区别。 present和dismiss 特点 在当前控制器上方新建视图层级需要手动调用…...