力扣labuladong一刷day61天动态规划最小下降路径

news/2024/2/23 16:22:26/文章来源:https://blog.csdn.net/qq_43511039/article/details/135618788

力扣labuladong一刷day61天动态规划最优子结构

一、931. 下降路径最小和

题目链接:https://leetcode.cn/problems/minimum-falling-path-sum/description/
如下图所示,求最小下降路径,定义dp[i][j]表示从最上面那行的任意位置抵达到nums[i][j]这个位置的最小路径和。根据题意每个位置只能从它上一行中的正上方的3个位置中得来,递推公式为dp[i][j]=min(dp[i-1][j-1], dp[i-1][j], dp[i-1][j+1])+nums[i][j],因为是下降路径,遍历顺序自然是从上往下,从左往右,没啥限制每个节点都得遍历,时间复杂度为n2。可以不new新的dp数组,直接在nums上做运算,空间复杂度1。
在这里插入图片描述

class Solution {public int minFallingPathSum(int[][] matrix) {int len = matrix.length, max = Integer.MAX_VALUE;for (int i = 1; i < matrix.length; i++) {for (int j = 0; j < matrix.length; j++) {int left = j-1>=0 ? matrix[i-1][j-1]:max;int mid = matrix[i-1][j];int right = j+1<len ? matrix[i-1][j+1]:max;matrix[i][j] = Math.min(Math.min(left, mid), right) + matrix[i][j];}}int min = Integer.MAX_VALUE;for (int i = 0; i < len; i++) {min = Math.min(min, matrix[len-1][i]);}return min;}
}

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

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

相关文章

Redis分布式锁--java实现

文章目录 Redis分布式锁方案&#xff1a;SETNX EXPIRE基本原理比较好的实现会产生四个问题 几种解决原子性的方案方案&#xff1a;SETNX value值是&#xff08;系统时间过期时间&#xff09;方案&#xff1a;使用Lua脚本(包含SETNX EXPIRE两条指令)方案&#xff1a;SET的扩展…

springcloud Alibaba中gateway和sentinel联合使用

看到这个文章相信你有一定的sentinel和gateway基础了吧。 官网的gateway和sentinel联合使用有些过时了&#xff0c;于是有了这个哈哈&#xff0c;给你看看官网的&#xff1a; 才sentinel1.6&#xff0c;现在都几了啊&#xff0c;所以有些过时。 下面开始讲解&#xff1a; 首先…

【Linux】自定义shell

👑作者主页:@安 度 因 🏠学习社区:安度因 📖专栏链接:Linux 文章目录 获取命令行前置字段命令行输入解析命令行普通指令的执行子进程执行命令指令类型判断 && 内建命令总结 &&a

【Maven】007-Maven 工程的继承和聚合关系

【Maven】007-Maven 工程的继承和聚合关系 文章目录 【Maven】007-Maven 工程的继承和聚合关系一、Maven 工程的继承关系1、继承的概念2、继承的作用3、继承的语法4、父工程统一管理依赖版本父工程声明依赖版本子工程继承以来版本 二、Maven 工程的聚合关系1、聚合的概念2、聚合…

VitePress-01-从零开始的项目创建(npm版)

说明 本文介绍一下 VitePress的项目创建的步骤。 主要用到的命令工具是 npm。 本文的操作步骤是从无到有的创建一个完整的基本的【VitePress】项目。 环境准备 根据官方文档的介绍&#xff0c;截止本文发稿时&#xff0c;需要使用node.js 18 的版本。 可以使用node -v 的命令查…

【MySQL】MySQL表的约束-空属性/默认值/列属性/zerofill/主键/自增长/唯一键/外键

文章目录 表的约束1.空属性 --null && not null2.默认值 -- default3.列描述4.zerofill5.主键6.自增长7.唯一键8.外键 表的约束 表的约束&#xff1a;表中一定要有各种约束&#xff0c;通过约束&#xff0c;让我们未来插入数据库表中的数据是符合预期的。约束的本质是…

【GCC】6 接收端实现:周期构造RTCP反馈包

基于m98代码。GCC涉及的代码,可能位于:webrtc/modules/remote_bitrate_estimator webrtc/modules/congestion_controller webrtc/modules/rtp_rtcp/source/rtcp_packet/transport_feedback.cc webrtc 之 RemoteEstimatorProxy 对 remote_bitrate_estimator 的 RemoteEstimato…

Spark与HBase的集成与数据访问

Apache Spark和Apache HBase分别是大数据处理和分布式NoSQL数据库领域的两个重要工具。在本文中&#xff0c;将深入探讨如何在Spark中集成HBase&#xff0c;并演示如何通过Spark访问和操作HBase中的数据。将提供丰富的示例代码&#xff0c;以便更好地理解这一集成过程。 Spark…

【EI会议征稿通知】第四届图像处理与智能控制国际学术会议(IPIC 2024)

第四届图像处理与智能控制国际学术会议&#xff08;IPIC 2024&#xff09; 2024 4th International Conference on Image Processing and Intelligent Control 2024年第四届图像处理与智能控制国际学术会议&#xff08;IPIC 2024&#xff09;将于2024年5月3日-5日在吉隆坡举…

【Jmeter之get请求传递的值为JSON体实践】

Jmeter之get请求传递的值为JSON体实践 get请求的常见传参方式 1、在URL地址后面拼接&#xff0c;有多个key和value时&#xff0c;用&链接 2、在Parameters里面加上key和value 第一次遇到value的值不是字符串也不是整型&#xff0c;我尝试把json放到value里面&#xff0…

C练习——杨辉三角

题目&#xff1a; 打印近似杨辉三角&#xff0c;行数n自选 百度找的杨辉三角&#xff0c;参考一下&#xff1a; 解析&#xff1a; 把它的全部元素左对齐&#xff0c;就可以看成近似杨辉三角的样子 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 …… 每个数等于它上方两数…

OpenCV C++ 环境搭建和简单示例

OpenCV介绍 OpenCV&#xff1a;开源发行的跨平台计算机视觉和机器学习软件库&#xff0c;用C语言编写&#xff0c;提供了C &#xff0c;Python&#xff0c;Java和MATLAB接口&#xff0c;并支持Windows&#xff0c;Linux&#xff0c;Android和Mac OS。 OpenCV下载 去官网http…

常见面试题之CSS

CSS3的新特性 新增选择器&#xff1a;:nth-child()、:first-of-type、:last-of-type等 弹性盒子&#xff1a;display: flex 媒体查询&#xff1a;media根据设备的特性和屏幕大小应用不同的样式规则 多列布局&#xff1a;column-count和column-with等属性可以实现将内容分为多…

蓝桥杯每日一题----货物摆放

题目 分析 上来一看&#xff0c;三个for循环&#xff0c;从1到n&#xff0c;寻找满足lwhn的个数&#xff0c;但是这样根本跑不出来答案&#xff0c;n太大了&#xff0c;1e15的级别&#xff0c;O&#xff08;n&#xff09;的时间复杂度都不行&#xff0c;更何况是O&#xff08;…

Webpack 怎么实现按需异步加载模块

要弄懂这个问题&#xff0c;需要先来看关于webpack打包的3个问题。 三个问题 第一个问题 项目中的json文件&#xff0c;如何使用webpack进行处理&#xff1f; 如果我们希望把json文件当做静态配置&#xff0c;例如有如下json文件 {"version": "1.0.0"…

高级 Python 面试问题与解答

文章目录 专栏导读1.什么是PIP&#xff1f;2.什么是 zip 函数&#xff1f;3.Python 中的 __init __ () 是什么&#xff1f;4.Python 中的访问说明符是什么&#xff1f;5.Python 中的单元测试是什么&#xff1f;6.Python全局解释器锁&#xff08;GIL&#xff09;&#xff1f;7.P…

Linux Debian12使用VSCode和Python搭建flask开发环境

一、安装VSCode 在Linux Debian12系统上安装VSCode教程可以参考网上相关教程。 二、安装Python 打开VSCode&#xff0c;安装python和python扩展包&#xff0c;如下图所示&#xff1a; 三、创建Python虚拟环境 1.新建文件夹testFlask 2.用vscode打开文件夹testFlask&#xf…

FFmpeg连载6-音频重采样

今天我们的实战内容是将音频解码成PCM&#xff0c;并将PCM重采样成特定的采样率&#xff0c;然后输出到本地文件进行播放。 什么是重采样&#xff1f; 所谓重采样&#xff0c;一句话总结就是改变音频的三元素&#xff0c;也就是通过重采样改变音频的采样率、采样格式或者声道数…

【docker-compose】【nginx】内网环境https配置

目录 1、openssl生成自签名证书和私钥2、nginx.conf配置ssl3、docker-compose挂载 1、openssl生成自签名证书和私钥 在部署服务器上&#xff0c;新建cert目录&#xff0c;执行以下指令&#xff0c;然后生成.crt和.key文件 openssl req -newkey rsa:2048 -nodes -keyout rsa_pri…

成都力寰璨泓科技有限公司:抖小店新势力

在当下这个信息爆炸的时代&#xff0c;科技的发展日新月异&#xff0c;电商行业更是风起云涌。在这场没有硝烟的战争中&#xff0c;成都力寰璨泓科技有限公司以其敏锐的商业洞察和卓越的技术实力&#xff0c;成功抢滩抖音小店市场&#xff0c;成为一股不可忽视的新生力量。 成都…