【算法|动态规划No.16】leetcode931. 下降路径最小和
个人主页:兜里有颗棉花糖
欢迎 点赞👍 收藏✨ 留言✉ 加关注💓本文由 兜里有颗棉花糖 原创
收录于专栏【手撕算法系列专栏】【LeetCode】
🍔本专栏旨在提高自己算法能力的同时,记录一下自己的学习过程,希望对大家有所帮助
🍓希望我们一起努力、成长,共同进步。
点击直接跳转到该题目
目录
- 1️⃣题目描述
- 2️⃣题目解析
- 3️⃣解题代码
1️⃣题目描述
给你一个 n x n 的 方形 整数数组 matrix ,请你找出并返回通过 matrix 的下降路径 的 最小和 。
下降路径 可以从第一行中的任何元素开始,并从每一行中选择一个元素。在下一行选择的元素和当前行所选元素最多相隔一列(即位于正下方或者沿对角线向左或者向右的第一个元素)。具体来说,位置 (row, col) 的下一个元素应当是 (row + 1, col - 1)、(row + 1, col) 或者 (row + 1, col + 1) 。
示例1:
输入:matrix = [[2,1,3],[6,5,4],[7,8,9]]
输出:13
解释:如图所示,为和最小的两条下降路径
示例2:
输入:matrix = [[-19,57],[-40,-5]]
输出:-59
解释:如图所示,为和最小的下降路径
注意:
n == matrix.length == matrix[i].length1 <= n <= 100-100 <= matrix[i][j] <= 100
2️⃣题目解析
初始化:
dp表多开辟了一块空间。这是因为在计算最小下降路径和时,每一行的路径和都依赖于上一行的路径和。为了简化边界条件的处理,我们可以在dp表的第一行和最后一行外分别多开辟一列,将这些额外的空间初始化为INT_MAX。这样,当计算最小路径和时,我们不必特殊处理边界情况,而是统一使用通用的递推公式。(简而言之,多开辟了一行两列的空间)
状态表示:
dp[i][j]表示到达(i,j)位置的最小下降路径和
状态转移方程:
dp[i][j] = max(max(dp[i-1][j-1],dp[i-1][j]),dp[i-1][j+1]) + matrix[i][j]
返回值:
循环遍历dp表中的所有有效位置:ret = min(ret,dp[n][i]);
for(int i = 1;i <= n;i++)
{ret = min(ret,dp[n][i]);
}
return ret;
3️⃣解题代码
class Solution {
public:int minFallingPathSum(vector<vector<int>>& matrix) {int n = matrix.size();vector<vector<int>> dp(n + 1,vector<int>(n + 2,INT_MAX));for(int i = 0;i < n + 2;i++) dp[0][i] = 0;for(int i = 1;i <= n;i++){for(int j = 1;j <= n;j++){int x = dp[i - 1][j - 1],y = dp[i - 1][j],z = dp[i - 1][j + 1];dp[i][j] = matrix[i - 1][j - 1] + min(min(x,y),z);}}int ret = INT_MAX;for(int i = 1;i <= n;i++){ret = min(ret,dp[n][i]);}return ret;}
};
最后通过啦!!!

相关文章:
【算法|动态规划No.16】leetcode931. 下降路径最小和
个人主页:兜里有颗棉花糖 欢迎 点赞👍 收藏✨ 留言✉ 加关注💓本文由 兜里有颗棉花糖 原创 收录于专栏【手撕算法系列专栏】【LeetCode】 🍔本专栏旨在提高自己算法能力的同时,记录一下自己的学习过程,希望…...
Jenkins 构建时动态获取参数
文章目录 问题简介Groovy 脚本配置进阶 问题 在做jenkins项目时,有些参数不是固定写死的,而是动态变化的,这时我们可以用 Active Choices 插件来远程调用参数 问题解决方案:执行构建前使用Groovy Scrip调用本地脚本,…...
android app开机自启动
参考文章: Android APP开机启动,安卓APP开发自启动,安卓启动后APP自动启动 Android让程序开机自动运行APP_安卓应用开机启动并打开软件_weijia3624的博客-CSDN博客...
XSS CSRF
XSS & CSRF xss:跨站脚本攻击:注入一些非法的脚本 csrf:冒充身份 XSS 反射型 /welcome:res.send(req.query.type) 输入什么就输出什么(httpOnly:false,但不是解决方案) 比如:?&…...
新加坡星银行项目组笔试题面试题
Java/Fullstack___开发常见问题收集:(根据个人面试岗位进行参考) 项目介绍部分 介绍最近做过的项目,项目中遇到的印象深刻的问题,如何解决?就项目用到的技术,自己的技术以及如何使用࿱…...
基于SpringBoot的智能物流管理系统
目录 前言 一、技术栈 二、系统功能介绍 顾客信息管理 员工信息管理 员工信息管理 门店信息管理 门店信息管理 订单信息管理 三、核心代码 1、登录模块 2、文件上传模块 3、代码封装 前言 随着信息技术在管理上越来越深入而广泛的应用,管理信息系统的实施…...
【开源电商网站】(2),使用docker-compose和dockerfile进行配置,设置自定义的镜像,安装插件,增加汉化包,支持中文界面汉化。
项目相关代代码地址 相关内容: https://blog.csdn.net/freewebsys/category_12461196.html 原文地址: https://blog.csdn.net/freewebsys/article/details/133666433 包括以下运行的详细代码: https://gitee.com/study-demo-all/oscommerc…...
HTML5开发实例-3D全景(ThreeJs全景Demo) 详解(图)
前言 在现在市面上很多全景H5的环境下,要实现全景的方式有很多,可以用css3直接构建也可以用基于threeJs的库来实现,还有很多别的制作全景的软件使用 本教学适用于未开发过3D全景的工程狮 如果觉得内容太无聊可以直接跳到最后 下载代码 理论 整个3D全景所用的相关理论就…...
springboot项目静态资源映射
1. springboot项目静态资源映射 import org.springframework.boot.web.client.RestTemplateBuilder; import org.springframework.context.annotation.Bean; import...
【Linux初阶】多线程1 | 页表的索引作用,线程基础(优缺点、异常、用途),线程VS进程,线程控制,C++多线程引入
文章目录 ☀️一、深入理解页表☀️二、Linux线程概念🌻1.什么是线程(重点)⚡(1)线程的概念⚡(2)线程库初识 🌻2.线程的优点🌻3.线程的缺点🌻4.线程异常&…...
Flink--9、双流联结(窗口联结、间隔联结)
星光下的赶路人star的个人主页 我还有改变的可能性,一想起这点,我就心潮澎湃 文章目录 1、基于时间的合流——双流联结(Join)1.1 窗口联结(Window Join)1.2 间隔联结(Interval Join)…...
家政服务行业做开发微信小程序可以实现什么功能
家政服务行业开发微信小程序可以实现多种功能,从而提升服务品质和效率,下面我们来详细介绍一些可能实现的功能。 一、展示服务信息 家政服务微信小程序可以展示各种服务信息,包括各类家政服务项目、价格、服务流程、服务人员信息等。用户可以…...
20哈希表-三数之和
目录 LeetCode之路——15. 三数之和 分析: 官方题解: LeetCode之路——15. 三数之和 给你一个整数数组 nums ,判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i ! j、i ! k 且 j ! k ,同时还满足 nums[i] nums[j] nu…...
JVM 运行时数据区和垃圾收集算法
在 《深入理解 Java 虚拟机》一书中,作者将运行时数据区和垃圾收集算法放在开头章节,说明了这两个知识点是进一步学习 JVM 的基础知识点,相比后续的 垃圾收集器和 JMM,它也更加的简单。 运行时数据区 运行时数据区是《Java 虚拟…...
Java基于SpringBoot的高校招生系统
博主介绍:✌程序员徐师兄、7年大厂程序员经历。全网粉丝30W、csdn博客专家、掘金/华为云/阿里云/InfoQ等平台优质作者、专注于Java技术领域和毕业项目实战✌ 文章目录 简介系统设计思路1 数据库设计2 系统整体设计 系统详细设计1系统功能模块2. 管理员功能模块3学生…...
6. Python使用Asyncio开发TCP服务器简单案例
1. 说明 在Python中开发TCP/IP服务器有两种方式,一种使用Socket,需要在py文件中引入对应的socket包,这种方式只能执行单项任务;另一种方式使用Asyncio异步编程,可以一次创建多个服务器执行不同的任务。 2. 接口说明 …...
景联文科技:AI大模型强势赋能,助力自动驾驶迭代升级
我国一直以来都将自动驾驶作为新兴产业发展的重点领域之一,工信部等相关部委出台了一系列自动驾驶发展战略、规划和标准,一些地方政府也在积极开展关于自动驾驶的地方立法,为自动驾驶技术的研发和应用提供更加具体的法律保障。例如࿰…...
多周期CPU设计
多周期CPU设计 指令类型clock skew 指令类型 在计算机体系结构中,指令可以分为不同的类型,通常有R-type、I-type和J-type指令。 R-type指令(Register-type指令): R-type指令通常用于执行寄存器之间的操作,…...
Go 复合类型之字典类型介绍
Go 复合类型之字典类型介绍 文章目录 Go 复合类型之字典类型介绍一、map类型介绍1.1 什么是 map 类型?1.2 map 类型特性 二.map 变量的声明和初始化2.1 方法一:使用 make 函数声明和初始化(推荐)2.2 方法二:使用复合字…...
对于无法直接获取URL的数据爬虫
在爬学校安全教育题库的时候发现题库分页实际上执行了一段js代码,如下图所示 点击下一页时是执行了函数doPostBack,查看页面源码如下 点击下一页后这段js提交了一个表单,随后后端返回对应数据,一开始尝试分析获取对应两个参数&a…...
Python|GIF 解析与构建(5):手搓截屏和帧率控制
目录 Python|GIF 解析与构建(5):手搓截屏和帧率控制 一、引言 二、技术实现:手搓截屏模块 2.1 核心原理 2.2 代码解析:ScreenshotData类 2.2.1 截图函数:capture_screen 三、技术实现&…...
利用ngx_stream_return_module构建简易 TCP/UDP 响应网关
一、模块概述 ngx_stream_return_module 提供了一个极简的指令: return <value>;在收到客户端连接后,立即将 <value> 写回并关闭连接。<value> 支持内嵌文本和内置变量(如 $time_iso8601、$remote_addr 等)&a…...
从WWDC看苹果产品发展的规律
WWDC 是苹果公司一年一度面向全球开发者的盛会,其主题演讲展现了苹果在产品设计、技术路线、用户体验和生态系统构建上的核心理念与演进脉络。我们借助 ChatGPT Deep Research 工具,对过去十年 WWDC 主题演讲内容进行了系统化分析,形成了这份…...
IGP(Interior Gateway Protocol,内部网关协议)
IGP(Interior Gateway Protocol,内部网关协议) 是一种用于在一个自治系统(AS)内部传递路由信息的路由协议,主要用于在一个组织或机构的内部网络中决定数据包的最佳路径。与用于自治系统之间通信的 EGP&…...
Opencv中的addweighted函数
一.addweighted函数作用 addweighted()是OpenCV库中用于图像处理的函数,主要功能是将两个输入图像(尺寸和类型相同)按照指定的权重进行加权叠加(图像融合),并添加一个标量值&#x…...
微信小程序 - 手机震动
一、界面 <button type"primary" bindtap"shortVibrate">短震动</button> <button type"primary" bindtap"longVibrate">长震动</button> 二、js逻辑代码 注:文档 https://developers.weixin.qq…...
Java多线程实现之Callable接口深度解析
Java多线程实现之Callable接口深度解析 一、Callable接口概述1.1 接口定义1.2 与Runnable接口的对比1.3 Future接口与FutureTask类 二、Callable接口的基本使用方法2.1 传统方式实现Callable接口2.2 使用Lambda表达式简化Callable实现2.3 使用FutureTask类执行Callable任务 三、…...
【学习笔记】深入理解Java虚拟机学习笔记——第4章 虚拟机性能监控,故障处理工具
第2章 虚拟机性能监控,故障处理工具 4.1 概述 略 4.2 基础故障处理工具 4.2.1 jps:虚拟机进程状况工具 命令:jps [options] [hostid] 功能:本地虚拟机进程显示进程ID(与ps相同),可同时显示主类&#x…...
Map相关知识
数据结构 二叉树 二叉树,顾名思义,每个节点最多有两个“叉”,也就是两个子节点,分别是左子 节点和右子节点。不过,二叉树并不要求每个节点都有两个子节点,有的节点只 有左子节点,有的节点只有…...
3-11单元格区域边界定位(End属性)学习笔记
返回一个Range 对象,只读。该对象代表包含源区域的区域上端下端左端右端的最后一个单元格。等同于按键 End 向上键(End(xlUp))、End向下键(End(xlDown))、End向左键(End(xlToLeft)End向右键(End(xlToRight)) 注意:它移动的位置必须是相连的有内容的单元格…...



