力扣动态规划基础版(矩阵型)

62.不同路径(唯一路径问题)

62. 不同路径icon-default.png?t=O83Ahttps://leetcode.cn/problems/unique-paths/

方法一:动态规划 

 找状态转移方程,也就是说它从左上角走到右下角,只能往右或者往下走,那么设置一个位置为(i,j)它只能从(i-1,j)或者(i,j-1)走过来那么它的状态转移方程就是除了这个还要去思考边界条件,如果i=0那么就不满足右侧的状态转移方程,同理j

= 0也不行,就是边上的那些数,可以考虑到边上的那些数都可以设置为1,也就是f(i,0)和f(0,j)都是1

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

优化空间复杂度:

这个唯一路径问题可以进行空间复杂度的优化 :由于 f(i,j) 仅与第 i 行和第 i−1 行的状态有关,因此我们可以使用滚动数组代替代码中的二维数组,使空间复杂度降低为 O(n)。

这个思路是。我们不需要存储每一个点,只需要存储它的上面一个点就行,再加上上一列的值即可,从第二行开始,每一行进行遍历只需要原始的值加上上一列的值。边界条件就是第一行都是1(很好想)

class Solution {public int uniquePaths(int m, int n) {//对于每一行,按列进行遍历//第一行先都设为1int f[] = new int[n];for(int i = 0; i < n; ++i){f[i] = 1;}//从第二行开始,对每一列进行遍历,它的f值只和它的前一列相关for(int i = 1; i < m; i++){for(int j = 1; j < n; j++){f[j]  += f[j - 1];//这个f[j]再每一次行遍历都更新,它就代表着上一次遍历的上一行的内容 }}return f[n - 1];}
}

方法二:排列组合

因为它只能向下走或者是向右走,所以就只有

从左上角到右下角的过程中,我们需要移动 m+n−2 次,其中有 m−1 次向下移动,n−1 次向右移动。因此路径的总数,就等于从 m+n−2 次移动中选择 m−1 次向下移动的方案数。实现这个排列组合的式子就行,其实实现这个技巧也是有讲究的,因为上面等于下面两个的和,所以位数是一样的,做一个循环,每一项相乘就行

class Solution {public int uniquePaths(int m, int n) {long ans = 1;for(int x =  n,y = 1; y < m; ++x,++y){ans = ans *x/y;}return (int)ans;}
}

64.最小路径和 

64. 最小路径和icon-default.png?t=O83Ahttps://leetcode.cn/problems/minimum-path-sum/还不错这道题自己写出来了,感觉就是前面那个题目的变式,状态转移方程就是第(i,j)个点的最小值由于只能向下或者向右,所以最小值就是它上面的或者左边的加上它自身的值。然后边界条件考虑(0,0),再考虑第一行和第一列。

class Solution {public int minPathSum(int[][] grid) {int m = grid.length;int n = grid[0].length;int dp[][] = new int [m][n];dp[0][0] = grid[0][0];for(int i = 1 ; i < m ;++i){dp[i][0] = dp[i -1][0] + grid[i][0];}for(int j = 1; j < n;++j){dp[0][j] = dp[0][j - 1] + grid[0][j];}for(int i = 1; i < m; i++){for(int j = 1; j < n; j++){dp[i][j] = grid[i][j] + Math.min(dp[i -1][j],dp[i][j - 1]);}}return dp[m -1][n -1];}
}

63.不同路径Ⅱ

63. 不同路径 IIicon-default.png?t=O83Ahttps://leetcode.cn/problems/unique-paths-ii/

这个其实大同小异,但是加了个障碍也就是说带障碍的要做个判断,如果他这是0,这条路就死了直接置为0

然后这次构建dp数组是多了一个空间确实好用 

class Solution {public int uniquePathsWithObstacles(int[][] obstacleGrid) {int m = obstacleGrid.length;int n = obstacleGrid[0].length;int dp[][] = new int [m+1][n+1];dp[1][1] = 1;for(int i = 1; i < m + 1; ++i){for(int j = 1;j < n + 1; ++j){if(obstacleGrid[i -1][j -1] == 1){dp[i][j] = 0;}else{dp[i][j] = Math.max(dp[i][j],dp[i - 1][j]+dp[i][j -1]);//这里的max是为了dp[1][1]}}}return dp[m][n];}
}

做完了这个题我又回头看第62题,确实是这样创建数组更舒服,我就又写了一版62的题解

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

对于63题我觉得不能用这钟方式,因为如果这样设置他的转移方程是求最小值,这样的话边界是0的情况下都算进去了,就错误了。

120.三角形最小路径和

方法一:动态规划 

120. 三角形最小路径和icon-default.png?t=O83Ahttps://leetcode.cn/problems/triangle/看到这个题目有点恍惚了,感觉是和以前的题目没啥区别,状态转移方程也是很好想,就是这一个的最小值就是上面和上面的左边的最小值加上这个值的min,但是三角形边界的情况还是特殊一点,因为就是比如在第i行的第0个发现j-1到达不了,以及在第i行的第i个发现在第i-1行的第i列也到达不了,所以要考虑这个两边的边界情况。其他的部分还是很像的,还需注意的是triangle是数组想取值用get

 for(int i = 1; i < m; ++i){dp[i][0] = dp[i -1][0] + triangle.get(i).get(0);for(int j =1;j < i; ++j){dp[i][j] = Math.min(dp[i -1][j -1],dp[i -1][j]) +triangle.get(i).get(j);}dp[i][i] = dp[i - 1][i - 1] + triangle.get(i).get(i);}

class Solution {public int minimumTotal(List<List<Integer>> triangle) {int m = triangle.size();int [][] dp = new int [m][m];dp[0][0] = triangle.get(0).get(0);for(int i = 1; i < m; ++i){dp[i][0] = dp[i -1][0] + triangle.get(i).get(0);for(int j =1;j < i; ++j){dp[i][j] = Math.min(dp[i -1][j -1],dp[i -1][j]) +triangle.get(i).get(j);}dp[i][i] = dp[i - 1][i - 1] + triangle.get(i).get(i);}int minTol = dp[m -1][0];for(int i = 1; i < m; i++){minTol = Math.min(minTol,dp[m -1][i]);}return minTol;}
}

931.下降路径最小和

931. 下降路径最小和icon-default.png?t=O83Ahttps://leetcode.cn/problems/minimum-falling-path-sum/这道题目其实和上一道的思路属于是殊途同归的,需要考虑这些形状的边界的情况,与三角形不同,这个要考虑左右两边,容易出错的点就是在考虑右边的时候注意下标m -1同时考虑最后一排的最小值。做过上面那道题,这道题可以轻松ac

class Solution {public int minFallingPathSum(int[][] matrix) {int m = matrix.length;int dp[][]  = new int [m][m];//初始化for(int i = 0; i < m; ++i){dp[0][i] = matrix[0][i];}for(int i = 1; i < m; ++i){dp[i][0] = matrix[i][0] + Math.min(dp[i - 1][0],dp[i -1][1]); for(int j = 1; j < m - 1; ++j){dp[i][j] = matrix[i][j] + Math.min(Math.min(dp[i -1][j -1],dp[i -1][j]),dp[i -1][j + 1]);}dp[i][m - 1] = matrix[i][m -1] + Math.min(dp[i -1][m -1],dp[i -1][m -2]);}int minres = dp[m -1][0];for(int i = 0; i < m; ++i){minres = Math.min(minres,dp[m -1][i]);}return minres;}
}

221.最大正方形 

221. 最大正方形icon-default.png?t=O83Ahttps://leetcode.cn/problems/maximal-square/

方法一:暴力

暴力来说的话还是比较好想的,就是先遍历一遍,如果有1就设置为res为1了,然后就找到这个左上角,去算一下潜在的最大正方形,再去遍历去找,先沿着对角线如果是1的话,就再看看其他地方是否满足,设置flag,如果不满足置为false

class Solution {public int maximalSquare(char[][] matrix) {int m = matrix.length;int n = matrix[0].length;int res = 0;if(matrix == null || matrix.length == 0 || matrix[0].length == 0){return res;}for(int i = 0; i < m; ++i){for(int j = 0; j < n; ++j){if(matrix[i][j] == '1'){res = Math.max(1,res);//计算可能的最大的正方形边长int currentMaxside = Math.min(m - i,n - j);for(int k = 1 ;k < currentMaxside; ++k){//判断新增的一列是否都是1boolean flag = true; if(matrix[i + k][j + k] == '0'){break;}for(int q = 0; q < k; ++q){if(matrix[i + k][j + q] == '0' || matrix[i + q][j + k] == '0'){flag = false;break;}}if(flag){res = Math.max(res,k + 1);}else{break;}}}}}int ress = res * res;return ress;}
}

方法二:动态规划

这个就有点秒了,考虑的是用 dp(i,j) 表示以 (i,j) 为右下角,且只包含 1 的正方形的边长最大值。

如果该位置的值是 1,则 dp(i,j) 的值由其上方、左方和左上方的三个相邻位置的 dp 值决定。具体而言,当前位置的元素值等于三个相邻位置的元素中的最小值加 1。

这样的话状态转移方程就可以用下面式子来表示

然后注意边界条件就是,如果在第一排或者第一列,瑞国他是1的话,dp[i][j]只能为1 

dp[i][j] = Math.min(Math.min(dp[i -1][j],dp[i - 1][j -1 ]),dp[i][j -1]) + 1
class Solution {public int maximalSquare(char[][] matrix) {int Maxres = 0;int rows = matrix.length;int columns = matrix[0].length;int [][] dp = new int [rows][columns];for(int i = 0; i < rows; ++i){for(int j = 0; j < columns; ++j){if(matrix[i][j] == '1'){if(i == 0 || j == 0){dp[i][j] = 1;}else{dp[i][j] = Math.min(Math.min(dp[i -1][j],dp[i - 1][j -1 ]),dp[i][j -1]) + 1;}Maxres = Math.max(Maxres,dp[i][j]);}}}int Maxsquare = Maxres * Maxres;return Maxsquare;}
}

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

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

相关文章

adb 常用命令汇总

目录 adb 常用命令 1、显示已连接的设备列表 2、进入设备 3、安装 APK 文件到设备 4、卸载指定包名的应用 5、从设备中复制文件到本地 6、将本地文件复制到设备 7、查看设备日志信息 8、重启设备 9、截取设备屏幕截图 10、屏幕分辨率 11、屏幕密度 12、显示设备的…

基于大语言模型(LLM)自主Agent 智能体综述

近年来,LLM(Large Language Model)取得了显著成功,并显示出了达到人类智能的巨大潜力。基于这种能力,使用LLM作为中央控制器来构建自助Agent,以获得类人决策能力。 Autonomous agents 又被称为智能体、Agent。指能够通过感知周围环境、进行规划以及执行动作来完成既定任务。…

node.js模块化分析

什么是Node.js模块化 Node.js中的模块化‌是指将一个大文件拆分成独立且相互依赖的多个小模块。每个JS文件被视为一个独立的模块&#xff0c;模块之间是互相不可见的。如果一个模块需要使用另一个模块&#xff0c;则需要使用指定的语法来引入该模块&#xff0c;并且只能使用模块…

openstack之guardian介绍与实例创建过程

运行特征 采集模块&#xff1a;扩展Ceilometer&#xff0c;采集存储网、业务网连通性、nova目录是否可读写&#xff1b; 收集模块&#xff1a;将采集到的数据存储到数据库中&#xff1b; 分析模块&#xff1a;根据采集的结果&#xff0c;分析各节点状态&#xff0c;并进行反向检…

C语言 -- qsort的简单使用

qsort函数 一、介绍二、语法格式三、使用函数从小到大从大到小 四、结语 一、介绍 qsort 函数是 C 标准库中的一个通用排序函数&#xff0c;用于对数组进行快速排序。它定义在 <stdlib.h> 头文件中。这个非常灵活&#xff0c;因为它允许用户指定数组的元素类型、数组的大…

unity3d————叉乘的知识点

一、向量叉乘的知识点 定义与公式&#xff1a; 向量叉乘的定义为&#xff1a;对于两个三维向量a和b&#xff0c;它们的叉乘结果是一个向量c&#xff0c;记为cab。叉乘的计算公式为&#xff1a;c(y1z2-y2z1)i(x2z1-x1z2)j(x1y2-x2y1)k&#xff0c;其中a(x1, y1, z1)&#xff0c;…

vue2和vue3在html中引用组件component方式不一样

我的vue版本是&#xff1a;20.17.0 一、在HTML中&#xff0c;引用组件格式区别。 vue2引用组件可以是file.vue格式&#xff0c;需要导入&#xff1a;<script src"https://unpkg.com/http-vue-loader"></script>才可以识别vue格式。 vue3引用组件格式是…

密码学知识点整理一:密码学概论

密码学是什么&#xff1f; 密码学是一门研究编制密码和破译密码的技术科学。 密码学&#xff0c;作为信息安全的核心技术之一&#xff0c;其重要性在于能够为信息传输提供安全保障&#xff0c;确保数据在存储或传输过程中的机密性、完整性与真实性不被破坏。从古至今&#x…

我谈正态分布——正态偏态

目录 pdf和cdf参数 标准正态分布期望和方差分布形态 3 σ 3\sigma 3σ原则 正态和偏态正态偏态瑞利分布偏度 (Skewness)峰度 (Kurtosis) 比较 正态分布的英文是Normal Distribution&#xff0c;normal是“正常”或“标准”的意思&#xff0c;中文翻译是正态&#xff0c;多完美的…

杨传辉:云+AI 时代的一体化数据库|OceanBase发布会实录

在 2024 OceanBase 年度发布会 上&#xff0c; OceanBase CTO 杨传辉进行了主题为《云和 AI 时代的一体化数据库战略思考》的演讲&#xff0c;本文为演讲实录&#xff0c;欢迎阅读。 视频观看可点击&#xff1a;https://www.oceanbase.com/video/9001825 各位 OceanBase 的客…

华为OD机试 - 无重复字符的元素长度乘积的最大值(Python/JS/C/C++ 2024 C卷 100分)

华为OD机试 2024E卷题库疯狂收录中&#xff0c;刷题点这里 专栏导读 本专栏收录于《华为OD机试真题&#xff08;Python/JS/C/C&#xff09;》。 刷的越多&#xff0c;抽中的概率越大&#xff0c;私信哪吒&#xff0c;备注华为OD&#xff0c;加入华为OD刷题交流群&#xff0c;…

【格式化查看JSON文件】coco的json文件内容都在一行如何按照json格式查看

文章目录 1.使用 Python 中的 json 库2. 使用浏览器3. notepad4. VSCode 如果COCO的JSON文件内容在一行显示&#xff0c;这通常意味着文件被压缩或者是在传输过程中出现了问题。 1.使用 Python 中的 json 库 想更好地查看 COCO 格式的 JSON 标签&#xff0c;可以将其格式化为更…

2025生物发酵展(济南)为生物制造产业注入新活力共谱行业新篇章

2025第十四届国际生物发酵展将于3月3-5日济南盛大举办&#xff01;产业链逐步完整&#xff0c;展会面积再创历史新高&#xff0c;展览面积较上届增涨至60000平方米&#xff0c;专业观众40000&#xff0c;品牌展商800&#xff0c;同期活动会议增加至50场&#xff0c;展会同期将举…

kafka里的consumer 是推还是拉?

大家好&#xff0c;我是锋哥。今天分享关于【kafka里的consumer 是推还是拉&#xff1f;】面试题&#xff1f;希望对大家有帮助&#xff1b; kafka里的consumer 是推还是拉&#xff1f; 1000道 互联网大厂Java工程师 精选面试题-Java资源分享网 在Kafka中&#xff0c;消费者&…

Visual Studio | 配置管理

文章目录 一、配置管理1、项目属性1.1、常规1.2、VC 目录1.3、C/C -> 常规1.4、C/C -> 预处理器1.5、C/C -> 预编译头1.6、连接器 -> 常规1.7、连接器 -> 输入 2、编辑2.1、显示空格或tab符 一、配置管理 1、项目属性 1.1、常规 字段功能目标平台版本用于生成…

Docker打包自己项目推到Docker hub仓库(windows10)

一、启用Hyper-V和容器特性 1.应用和功能 2.点击程序和功能 3.启用或关闭Windows功能 4.开启Hyper-V 和 容器特性 记得重启生效&#xff01;&#xff01;&#xff01; 二、安装WSL2&#xff1a;写文章-CSDN创作中心https://mp.csdn.net/mp_blog/creation/editor/143057041 三…

js.轮转数组和旋转链表

这是两个相似的题型&#xff0c;一个是数组&#xff0c;另一个是链表。 链接&#xff1a;189. 轮转数组 - 力扣&#xff08;LeetCode&#xff09; 题目&#xff1a; 给定一个整数数组 nums&#xff0c;将数组中的元素向右轮转 k 个位置&#xff0c;其中 k 是非负数。 示例 1:…

mysql left join group_concat 主表丢失数据

问题出现的场景&#xff1a; 有一个主表 a&#xff0c;一个子表 b a表有两条数据&#xff0c;a表第一条数据在b表中有一条子数据&#xff0c;a表第二条数据在b表中有两条子数据。 现在想要查询出来a表的所有数据和a表的子表b的id&#xff0c;b的id 使用GROUP_CONCAT拼接 有…

Spring 中循环依赖 三级缓存

在Spring框架中&#xff0c;循环依赖是一个常见的问题&#xff0c;它指的是两个或多个Bean之间互相依赖&#xff0c;形成一个闭环&#xff0c;导致无法准确地完成对象的创建和初始化。为了解决这个问题&#xff0c;Spring引入了三级缓存机制。以下是对Spring中循环依赖和三级缓…

新能源汽车与公共充电桩布局

近年来,全球范围内对新能源汽车产业的推动力度不断增强,中国新能源汽车市场也呈现蓬勃发展的势头,在政策与市场的共同推动下,新能源汽车销量持续增长。然而,据中国充电联盟数据显示,充电基础设施建设滞后于新能源汽车数量增长的现状导致充电桩供需不平衡,公共充电桩服务空白区域…