【算法|动态规划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…...
宝塔面板计划任务设置教程
宝塔面板的计划任务,就是服务器的定时执行工具,不用手动敲命令,可视化界面就能设置,能实现自动备份、定时重启、清理缓存、执行脚本等多种自动化操作。下面详细讲解完整设置步骤、常用任务配置和避坑技巧。一、进入计划任务页面1.…...
三步解锁Bruno API测试工具的隐藏潜力
三步解锁Bruno API测试工具的隐藏潜力 【免费下载链接】bruno 开源的API探索与测试集成开发环境(作为Postman/Insomnia的轻量级替代方案) 项目地址: https://gitcode.com/GitHub_Trending/br/bruno Bruno作为Postman的开源替代品,以其…...
保姆级教程:用PyTorch 1.13+Win11搞定MSTAR数据集分类(附完整代码)
从零实现MSTAR数据集分类:PyTorch全卷积网络实战指南 1. 环境配置与工具准备 在Windows 11系统上搭建PyTorch开发环境需要特别注意版本兼容性问题。以下是经过验证的稳定组合: PyTorch 1.13.0 CUDA 11.6 cuDNN 8.3.2Python 3.8-3.10(推荐…...
通义千问3-Reranker-0.6B入门指南:app.py核心逻辑解析+自定义路由扩展
通义千问3-Reranker-0.6B入门指南:app.py核心逻辑解析自定义路由扩展 1. 引言 如果你正在寻找一个既轻量又强大的中文重排序模型,那么通义千问3-Reranker-0.6B绝对值得你花时间了解一下。这个只有6亿参数的模型,在文本检索和排序任务上的表…...
RexUniNLU新手入门指南:3步搞定智能家居、金融、医疗场景意图识别
RexUniNLU新手入门指南:3步搞定智能家居、金融、医疗场景意图识别 1. 认识RexUniNLU:零样本意图识别利器 RexUniNLU是一款基于Siamese-UIE架构的轻量级自然语言理解框架,它能让你无需准备标注数据,仅通过简单的标签定义就能完成…...
Monocle2拟时基因富集分析实战:从热图模块到通路解析
1. Monocle2拟时分析基础回顾 如果你正在做单细胞转录组分析,肯定对拟时分析(Pseudotime Analysis)不陌生。简单来说,这就像给细胞拍"成长视频",把静态的细胞状态连成动态的发展轨迹。Monocle2作为这个领域的…...
青少年软编等考六级题解目录
这个专栏发布中国电子学会主办的青少年软件编程等级考试 C 语言六级题目解析,每篇文章包含一次考试的全部 444 道题目的思路解析。由于考级允许使用 C/C 语言,因此解析中给出的参考代码均为 C 代码。为了方便大家查找,特此发布一篇文章作为目…...
16张动图解析网络基础原理与应用
16张动图趣味解读网络原理1. 网络基础概念1.1 网络的定义与作用网络存在于日常生活中的每一个角落,电脑、打印机、手机、电视等设备都属于网络设备。通过网络连接这些设备,可以实现数据传输和共享,让工作生活更加便捷。典型的网络应用场景包括…...
通义千问1.5-1.8B-Chat-GPTQ-Int4 Java开发集成:SpringBoot项目实战指南
通义千问1.5-1.8B-Chat-GPTQ-Int4 Java开发集成:SpringBoot项目实战指南 最近在帮一个朋友做项目,他们想在自己的Java应用里加个智能对话功能,看中了通义千问1.5-1.8B-Chat-GPTQ-Int4这个模型。这模型挺有意思的,体积小但能力不弱…...
手把手教你解决winget的InternetOpenUrl() failed错误(含GitHub镜像加速)
深度解析winget的InternetOpenUrl() failed错误及高效解决方案 当你满怀期待地打开终端,准备用winget快速安装一个开发工具时,突然跳出的"InternetOpenUrl() failed. 0x80072efd"错误提示无疑是一盆冷水。这个看似简单的网络连接问题背后&…...



