算法28:力扣64题,最小路径和------------样本模型

题目:

给定一个二维数组matrix,一个人必须从左上角出发,最后到达右下角 。沿途只可以向下或者向右走,沿途的数字都累加就是距离累加和 * 返回累加和最小值

思路:

1. 既然是给定二维数组matrix,那么二维数组的数据是知道的

2. 这个人只能从左上角出发,目的地是右下角

3. 沿途只能向下或者向右走。那么第一行和第一列的值是可以知道的。

假设这个二维数组是:

3796
6539
8315
4792

根据这个二维数组推导:

第一行的数据只能往右走,因为它不存在上方数据,依此可以推导出:

3101925

第一列的数据,只能往下走,因为它不存在左边的数据,以此可以推导

310(3+7)19(10+9)25(19+6)
9(3+6)
17(9+8)
21(17+4)

已经推导出第一行和第一列的数据,接下来开始推导剩下的数据。因为每一个格子的数据都是依赖上一行的当前列或者当前行的前一列的值。谁小,就要谁。以此可以推导出:

3101925
914(9<10取 9+5)17(14<19 取14+3)26(17<25 取17+9)
1717(14<17 取14+3)1823(18<26 取 18+5)
2124 (17<21 取 17+7)27 (18<24 取 18+9)25 (23<27 取 23+2)

推导公式已经出来了。下面看代码的实现:

public static int minSum (int[][] matrix){if (matrix == null || matrix.length == 0) {return 0;}//行数int row = matrix.length;//列数int col = matrix[0].length;//如果是100*100规模的二维数组。那么dp的空间开销巨大int[][] dp = new int[row][col];//dp的第一行值只能依赖左边的值dp[0][0] = matrix[0][0];//构建dp表的第一行数据for (int colIndex = 1; colIndex < col; colIndex++) {//前一列和当前列的累加和,放入dp表dp[0][colIndex] = dp[0][colIndex -1] + matrix[0][colIndex];}//构建dp表的第一列数据for (int rowIndex = 1; rowIndex < row; rowIndex++) {//上一列和当前列的累加和,放入dp表dp[rowIndex][0] = dp[rowIndex -1][0] + matrix[rowIndex][0];}for (int rowIndex = 1; rowIndex < row; rowIndex++) {for (int colIndex = 1; colIndex < col; colIndex++) {//先获取上一行当前列 与 当前行的前一列 较小的值//获取matrix数组的当前行当前列的值//两者相加,就是 dp[rowIndex][colIndex]能够得到的最小值dp[rowIndex][colIndex] = Math.min(dp[rowIndex][colIndex -1], dp[rowIndex -1][colIndex]) + matrix[rowIndex][colIndex];}}return dp[row-1][col-1];}

以上代码是逐步推导的过程。但是,如果一个100行100列的数组需要推导,而且是要右下角的数据,中间数据是没有必要一直存在的。以上的代码浪费了 100*100的空间,并不是一个好的方式:

分析:

1. 第一行的数据是一定要的,因为根据第一行数据可以推导出第二行的数据

2. 第一列的数据是没有必要一次性全部推导出来的,因为每一个格子只依赖上一行的当前列和当前行的前一列。如果移动到当前行,直接更新当前行的第一列即可。

优化的代码:

//空间压缩进行优化public static int minSum2 (int[][] matrix){if (matrix == null || matrix.length == 0) {return 0;}//行数int row = matrix.length;//列数int col = matrix[0].length;// 空间压缩。// 二维数组变一维数组。int[] dp = new int[col];//构建dp表的第一行数据dp[0] = matrix[0][0];for (int colIndex = 1; colIndex < col; colIndex++) {//前一列和当前列的累加和,放入dp表dp[colIndex] = dp[colIndex -1] + matrix[0][colIndex];}for (int rowIndex = 1; rowIndex < row; rowIndex++) {//当前行第一列数据dp[0] += matrix[rowIndex][0];for (int colIndex = 1; colIndex < col; colIndex++) {dp[colIndex] = Math.min(dp[colIndex -1], dp[colIndex]) + matrix[rowIndex][colIndex];}}return dp[col -1];}

完整代码以及测试结果:

package code03.动态规划_07.lesson4;/*** 给定一个二维数组matrix,一个人必须从左上角出发,最后到达右下角* 沿途只可以向下或者向右走,沿途的数字都累加就是距离累加和* 返回累加和最小值*/
public class MinPathSum_01 {public static int minSum (int[][] matrix){if (matrix == null || matrix.length == 0) {return 0;}//行数int row = matrix.length;//列数int col = matrix[0].length;//如果是100*100规模的二维数组。那么dp的空间开销巨大int[][] dp = new int[row][col];//dp的第一行值只能依赖左边的值dp[0][0] = matrix[0][0];//构建dp表的第一行数据for (int colIndex = 1; colIndex < col; colIndex++) {//前一列和当前列的累加和,放入dp表dp[0][colIndex] = dp[0][colIndex -1] + matrix[0][colIndex];}//构建dp表的第一列数据for (int rowIndex = 1; rowIndex < row; rowIndex++) {//上一列和当前列的累加和,放入dp表dp[rowIndex][0] = dp[rowIndex -1][0] + matrix[rowIndex][0];}for (int rowIndex = 1; rowIndex < row; rowIndex++) {for (int colIndex = 1; colIndex < col; colIndex++) {//先获取上一行当前列 与 当前行的前一列 较小的值//获取matrix数组的当前行当前列的值//两者相加,就是 dp[rowIndex][colIndex]能够得到的最小值dp[rowIndex][colIndex] = Math.min(dp[rowIndex][colIndex -1], dp[rowIndex -1][colIndex]) + matrix[rowIndex][colIndex];}}return dp[row-1][col-1];}//空间压缩进行优化public static int minSum2 (int[][] matrix){if (matrix == null || matrix.length == 0) {return 0;}//行数int row = matrix.length;//列数int col = matrix[0].length;// 空间压缩。// 二维数组变一维数组。int[] dp = new int[col];//构建dp表的第一行数据dp[0] = matrix[0][0];for (int colIndex = 1; colIndex < col; colIndex++) {//前一列和当前列的累加和,放入dp表dp[colIndex] = dp[colIndex -1] + matrix[0][colIndex];}for (int rowIndex = 1; rowIndex < row; rowIndex++) {//当前行第一列数据dp[0] += matrix[rowIndex][0];for (int colIndex = 1; colIndex < col; colIndex++) {dp[colIndex] = Math.min(dp[colIndex -1], dp[colIndex]) + matrix[rowIndex][colIndex];}}return dp[col -1];}public static void main(String[] args) {int[][] arr = {{3,7,9,6},{6,5,3,9},{8,3,1,5},{4,7,9,2}};System.out.println(minSum(arr));System.out.println(minSum2(arr));}}

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

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

相关文章

element el-table实现可进行横向拖拽滚动

【问题】表格横向太长&#xff0c;表格横向滚动条位于最底部&#xff0c;需将页面滚动至最底部才可左右拖动表格&#xff0c;用户体验感不好 【需求】基于elment的el-table组件生成的表格&#xff0c;使其可以横向拖拽滚动 【实现】灵感来源于这篇文章【Vue】表格可拖拽滚动&am…

C++摸版(初阶)----函数模版与类模版

本专栏内容为&#xff1a;C学习专栏&#xff0c;分为初阶和进阶两部分。 通过本专栏的深入学习&#xff0c;你可以了解并掌握C。 &#x1f493;博主csdn个人主页&#xff1a;小小unicorn ⏩专栏分类&#xff1a;C &#x1f69a;代码仓库&#xff1a;小小unicorn的代码仓库&…

大数据StarRocks(二) StarRocks集群部署

一、生产机器资源评估 1.梳理数据量&#xff0c;包括每天增量数据接入和全量数据接入 2.数据存储时间长度&#xff08;1个月/3个月/半年/1年/三年等&#xff09; 3.报表的SQL查询数量&#xff0c;SQL查询占用资源的统计&#xff0c;需要提前做好压测 4.压测可以采用官网提供的…

C++Qt6 多种排序算法的比较 数据结构课程设计 | JorbanS

一、 问题描述 在计算机科学与数学中&#xff0c;一个排序算法&#xff08;英语&#xff1a;Sorting algorithm&#xff09;是一种能将一串资料依照特定排序方式排列的算法。最常用到的排序方式是数值顺序以及字典顺序。有效的排序算法在一些算法&#xff08;例如搜索算法与合…

STM32F407-14.3.10-表73具有有断路功能的互补通道OCx和OCxN的输出控制位-01x00

如上表所示&#xff0c;MOE0&#xff0c;OSSI1&#xff0c;CCxE0&#xff0c;CCxNE0时&#xff0c;OCx与OCxN的输出状态取决于GPIO端口上下拉状态。 ---------------------------------------------------------------------------------------------------------------------…

web前端开发网页制作html/css结课作业

效果图展示&#xff1a; 注意事项&#xff1a; 引用JQuery文件地址和图片地址要更换一下。 百度网盘链接&#xff1a; http://链接&#xff1a;https://pan.baidu.com/s/1wYkmLr7csjBwQY6GmlYm4Q?pwd4332 提取码&#xff1a;4332 html界面展示&#xff1a; main.css代码部…

JavaScript:作用域变量回收

JavaScript&#xff1a;作用域&变量回收 局部作用域函数作用域块作用域 全局作用域作用域链变量在浏览器模型中的位置浏览器模型全局变量的产生情况直接赋值全局对象与var全局对象的区别 垃圾回收机制引用计数法标记清除法 闭包变量提升&函数提升 作用域规定了变量能够…

Zookeeper之Java客户端实战

ZooKeeper应用的开发主要通过Java客户端API去连接和操作ZooKeeper集群。可供选择的Java客户端API有&#xff1a; ZooKeeper官方的Java客户端API。第三方的Java客户端API&#xff0c;比如Curator。 接下来我们将逐一学习一下这两个java客户端是如何操作zookeeper的。 1. ZooKe…

[DAU-FI Net开源 | Dual Attention UNet+特征融合+Sobel和Canny等算子解决语义分割痛点]

文章目录 概要I Introduction小结 概要 提出的架构&#xff0c;双注意力U-Net与特征融合&#xff08;DAU-FI Net&#xff09;&#xff0c;解决了语义分割中的挑战&#xff0c;特别是在多类不平衡数据集上&#xff0c;这些数据集具有有限的样本。DAU-FI Net 整合了多尺度空间-通…

C#使用 OpenHardwareMonitor获取CPU或显卡温度、使用率、时钟频率相关方式

C# 去获取电脑相关的基础信息&#xff0c;还是需要借助 外部的库&#xff0c;我这边尝试了自己去实现它 网上有一些信息&#xff0c;但不太完整&#xff0c;都比较零碎&#xff0c;这边尽量将代码完整的去展示出来 OpenHardwareMonitor获取CPU的温度和频率需要管理员权限 在没…

opencv003图像裁剪(应用NumPy矩阵的切片)

这一部分相对于马上要学习的二值化是要更更更简单一些的&#xff0c;只需三行&#xff0c;便能在opencv上裁剪图像啦&#xff08;顺便云吸猫&#xff0c;太可爱了&#xff01;&#xff09; 出处见水印&#xff01; 1、复习图像的显示 前几天期末考试&#xff0c;太久没有看…

Unity中Shader的Reversed-Z(DirectX平台)

文章目录 前言一、在对裁剪坐标归一化设置NDC时&#xff0c;DirectX平台Z的特殊二、在图形计算器中&#xff0c;看一下Z值反转前后变化1、在图形计算器创建两个变量 n 和 f 分别 控制近裁剪面 和 远裁剪面2、带入公式得到齐次裁剪空间下Z值3、进行透视除法4、用 1 - Z 得出Z值反…

是否需要跟上鸿蒙(OpenHarmony)开发岗位热潮?

前言 自打华为2019年发布鸿蒙操作系统以来&#xff0c;网上各种声音百家争鸣。尤其是2023年发布会公布的鸿蒙4.0宣称不再支持Android&#xff0c;更激烈的讨论随之而来。 本文没有宏大的叙事&#xff0c;只有基于现实的考量。 通过本文&#xff0c;你将了解到&#xff1a; Har…

电脑如何屏幕录制?轻松录制高清视频

在当今信息化的时代&#xff0c;电脑已经成为工作和生活的重要工具。无论是在进行演示、教学还是记录重要操作步骤时&#xff0c;屏幕录制都是非常有用的。可是电脑如何屏幕录制呢&#xff1f;本篇文章将介绍三种常见的电脑屏幕录制方法&#xff0c;通过学习这些方法&#xff0…

【Pytorch】学习记录分享10——PyTorchTextCNN用于文本分类处理

【Pytorch】学习记录分享10——PyTorchTextCNN用于文本分类处理 1. TextCNN用于文本分类2. 代码实现 1. TextCNN用于文本分类 具体流程&#xff1a; 2. 代码实现 # coding: UTF-8 import torch import torch.nn as nn import torch.nn.functional as F import numpy as np…

《异常检测——从经典算法到深度学习》25 基于深度隔离林的异常检测算法

《异常检测——从经典算法到深度学习》 0 概论1 基于隔离森林的异常检测算法 2 基于LOF的异常检测算法3 基于One-Class SVM的异常检测算法4 基于高斯概率密度异常检测算法5 Opprentice——异常检测经典算法最终篇6 基于重构概率的 VAE 异常检测7 基于条件VAE异常检测8 Donut: …

案例086:基于微信小程序的影院选座系统

文末获取源码 开发语言&#xff1a;Java 框架&#xff1a;SSM JDK版本&#xff1a;JDK1.8 数据库&#xff1a;mysql 5.7 开发软件&#xff1a;eclipse/myeclipse/idea Maven包&#xff1a;Maven3.5.4 小程序框架&#xff1a;uniapp 小程序开发软件&#xff1a;HBuilder X 小程序…

【数字图像处理技术与应用】2023-2024上图像处理期中-云南农业大学

一、填空题&#xff08;每空2 分&#xff0c;共 30 分&#xff09; 1、图像就是3D 场景在 二维 平面上的影像&#xff0c;根据其存储方式和表现形式&#xff0c;可以将图像分为 模拟 图像和数字图像两大类&#xff1b; 2、在用计算机对数字图像处理中&#xff0c;常用一个 二…

计算机专业个人简历范文(8篇)

HR浏览一份简历也就25秒左右&#xff0c;如果你连「好简历」都没有&#xff0c;怎么能找到好工作呢&#xff1f; 如果你不懂得如何在简历上展示自己&#xff0c;或者觉得怎么改简历都不出彩&#xff0c;那请你一定仔细读完。 互联网运营个人简历范文> 男 22 本科 AI简历…

【JVM】一文掌握JVM垃圾回收机制

作为Java程序员,除了业务逻辑以外,随着更深入的了解,都无法避免的会接触到JVM以及垃圾回收相关知识。JVM调优是一个听起来很可怕,实际上很简单的事。 感到可怕,是因为垃圾回收相关机制都在JVM的C++层实现,我们在Java开发中看不见摸不着;而实际很简单,是因为它说到底,也…