算法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…...

JavaSec-RCE
简介 RCE(Remote Code Execution),可以分为:命令注入(Command Injection)、代码注入(Code Injection) 代码注入 1.漏洞场景:Groovy代码注入 Groovy是一种基于JVM的动态语言,语法简洁,支持闭包、动态类型和Java互操作性,…...

.Net框架,除了EF还有很多很多......
文章目录 1. 引言2. Dapper2.1 概述与设计原理2.2 核心功能与代码示例基本查询多映射查询存储过程调用 2.3 性能优化原理2.4 适用场景 3. NHibernate3.1 概述与架构设计3.2 映射配置示例Fluent映射XML映射 3.3 查询示例HQL查询Criteria APILINQ提供程序 3.4 高级特性3.5 适用场…...
渲染学进阶内容——模型
最近在写模组的时候发现渲染器里面离不开模型的定义,在渲染的第二篇文章中简单的讲解了一下关于模型部分的内容,其实不管是方块还是方块实体,都离不开模型的内容 🧱 一、CubeListBuilder 功能解析 CubeListBuilder 是 Minecraft Java 版模型系统的核心构建器,用于动态创…...
unix/linux,sudo,其发展历程详细时间线、由来、历史背景
sudo 的诞生和演化,本身就是一部 Unix/Linux 系统管理哲学变迁的微缩史。来,让我们拨开时间的迷雾,一同探寻 sudo 那波澜壮阔(也颇为实用主义)的发展历程。 历史背景:su的时代与困境 ( 20 世纪 70 年代 - 80 年代初) 在 sudo 出现之前,Unix 系统管理员和需要特权操作的…...

c#开发AI模型对话
AI模型 前面已经介绍了一般AI模型本地部署,直接调用现成的模型数据。这里主要讲述讲接口集成到我们自己的程序中使用方式。 微软提供了ML.NET来开发和使用AI模型,但是目前国内可能使用不多,至少实践例子很少看见。开发训练模型就不介绍了&am…...

蓝桥杯3498 01串的熵
问题描述 对于一个长度为 23333333的 01 串, 如果其信息熵为 11625907.5798, 且 0 出现次数比 1 少, 那么这个 01 串中 0 出现了多少次? #include<iostream> #include<cmath> using namespace std;int n 23333333;int main() {//枚举 0 出现的次数//因…...
探索Selenium:自动化测试的神奇钥匙
目录 一、Selenium 是什么1.1 定义与概念1.2 发展历程1.3 功能概述 二、Selenium 工作原理剖析2.1 架构组成2.2 工作流程2.3 通信机制 三、Selenium 的优势3.1 跨浏览器与平台支持3.2 丰富的语言支持3.3 强大的社区支持 四、Selenium 的应用场景4.1 Web 应用自动化测试4.2 数据…...

若依登录用户名和密码加密
/*** 获取公钥:前端用来密码加密* return*/GetMapping("/getPublicKey")public RSAUtil.RSAKeyPair getPublicKey() {return RSAUtil.rsaKeyPair();}新建RSAUti.Java package com.ruoyi.common.utils;import org.apache.commons.codec.binary.Base64; im…...
二维FDTD算法仿真
二维FDTD算法仿真,并带完全匹配层,输入波形为高斯波、平面波 FDTD_二维/FDTD.zip , 6075 FDTD_二维/FDTD_31.m , 1029 FDTD_二维/FDTD_32.m , 2806 FDTD_二维/FDTD_33.m , 3782 FDTD_二维/FDTD_34.m , 4182 FDTD_二维/FDTD_35.m , 4793...
window 显示驱动开发-如何查询视频处理功能(三)
D3DDDICAPS_GETPROCAMPRANGE请求类型 UMD 返回指向 DXVADDI_VALUERANGE 结构的指针,该结构包含特定视频流上特定 ProcAmp 控件属性允许的值范围。 Direct3D 运行时在D3DDDIARG_GETCAPS的 pInfo 成员指向的变量中为特定视频流的 ProcAmp 控件属性指定DXVADDI_QUER…...