当前位置: 首页 > news >正文

动态规划 —— 路径问题-最小路径和

1. 最小路径和

题目链接:

64. 最小路径和 - 力扣(LeetCode)icon-default.png?t=O83Ahttps://leetcode.cn/problems/minimum-path-sum/description/

 


2.  算法原理

状态表示:以莫一个位置位置为结尾

   

dp[i,j]表示:到达[i,j]位置的时候,此时的最小路径和

2. 状态转移方程

  

根据最近的一步来划分问题:

   

到达dp[i][j]有两种情况:

                                        1. 从上面过来:[i-1,j] -> [i,j],dp[i-1,j] + g[i][j]

        

                                        2. 从左边过来:[i,j-1] -> [i,j],dp[i,j-1] + g[i][j]
    

本题的状态转移方程是:dp[i][j] = min(dp[i-1,j] ,dp[i,j-1])+ g[i][j]

3. 初始化 :把dp表填满不越界,让后面的填表可以顺利进行

   

我们可以在上面的一行和左边的一列再额外的加上一行和一列的虚拟节点

          

          

初始化时可以先将所有的虚拟节点初始化为正无穷大,然后再把原始矩阵的第一个值的上方和左边的虚拟节点初始化为0,因为不能让虚拟节点的值干扰到原始矩阵节点的值

    

本题的下标映射关系:因为本题给了一个矩阵,而我们又额外的加上一行和一列的虚拟节点,所以我们的下标都统一往右下角移动了一位,如果想找回之前对应的位置,那么下标需要进行统一减1(横纵坐标)

4. 填表顺序 

    

本题的填表顺序是:从上往下填写每一行,每一行的值是从左往右

 

5. 返回值 :题目要求 + 状态表示 

    

本题的返回值是:dp[m][n]


3.代码 

动态规划的固定四步骤:1.  创建一个dp表

                                        2. 在填表之前初始化

                                        3. 填表(填表方法:状态转移方程)

                                        4. 确定返回值 

class Solution {
public:int minPathSum(vector<vector<int>>& grid) {int m=grid.size(),n=grid[0].size();//创建dp表随便将虚拟节点全部初始化为正无穷大vector<vector<int>>dp(m+1,vector<int>(n+1,INT_MAX));//再将dp[0][1]和dp[1][0]初始化为0dp[0][1]=dp[1][0]=0;for (int i = 1; i <= m; i++)for (int j = 1; j <= n; j++)//这里的grid[i-1][j-1]也是加上一行和一列的虚拟节点,所以要横纵-1dp[i][j]=min(dp[i - 1][j], dp[i][j - 1]) + grid[i - 1][j - 1];return dp[m][n];}
};


完结撒花~ 

相关文章:

动态规划 —— 路径问题-最小路径和

1. 最小路径和 题目链接&#xff1a; 64. 最小路径和 - 力扣&#xff08;LeetCode&#xff09;https://leetcode.cn/problems/minimum-path-sum/description/ 2. 算法原理 状态表示&#xff1a;以莫一个位置位置为结尾 dp[i&#xff0c;j]表示&#xff1a;到达[i&#xff0c;j…...

《链表篇》---删除链表的倒数第N个节点(中等)

题目传送门 方法一&#xff1a;计算链表长度&#xff08;迭代&#xff09; 1.计算链表长度&#xff0c;并且定义哑节点链接链表。 2.从哑节点开始前进length-n次。即为被删除节点的前置节点。 3.进行删除操作。 4.返回哑节点的后置节点 class Solution {public ListNode remo…...

duilib 进阶 之 TileListBox 列表

目录 一、TileListBox 1、样式 1)、整体列表分列设置 2)、列表项样式设置 3)、选中后出现√号,horver时 出现边框色 的实例 2、代码 1)、普通动态添加列表项 2)、列表项样式中有自定义控件时 3)、获得选中项 一、TileListBox Tile [taɪl] ,瓦片 棋子 Ti…...

Web应用安全—信息泄露

从书本和网上了解到Web应用安全的信息泄露的知识&#xff0c;今天跟大家分享点。 robots.txt泄漏敏感信息 漏洞描述&#xff1a;搜索引擎可以通过robots文件可以获知哪些页面可以爬取&#xff0c;哪些页面不可以爬取。Robots协议是网站国际互联网界通行的道德规范&#xff0c…...

大数据治理:策略、技术与挑战

随着信息技术的飞速发展&#xff0c;大数据已经成为现代企业运营和决策的重要基础。然而&#xff0c;大数据的复杂性、多样性和规模性给数据管理带来了前所未有的挑战。因此&#xff0c;大数据治理应运而生&#xff0c;成为确保数据质量、合规性、安全性和可用性的关键手段。本…...

vscode插件-08 Golang

文章目录 Go安装其他必须软件 Go Go语言环境&#xff0c;只需安装这一个插件。然后通过vscode命令下载安装其他go环境需要的内容。 程序调试&#xff0c;需要创建.vscode文件夹并编写launch.json文件。 安装其他必须软件 ctrlshiftp&#xff0c;调出命令面板&#xff0c;输入…...

数据结构+算法分析与设计[15-18真题版]

2015年考试试题 一、给出数组A[3..8,2..6]0F integer,当它在内存中按行存放和按列存放时&#xff0c;分别写出元素A[i,j]的地址计算公式(设每个元素占两个存储单元)。(10分) 二、已知一棵二叉树的中序序列的结果是BDCEAFHG,后序序列的结果是DECBHGFA,试画出这棵二叉树。(10分…...

单链表OJ题(2):反转链表(三指针法)、找中间节点(快慢指针)

目录 1.反转链表 反转链表总结&#xff1a; 2.链表的中间节点&#xff08;快慢指针法&#xff09; 快慢指针法总结 1.反转链表 在这道题中&#xff0c;我们需要把一个单链表反转它们的指向&#xff0c;这里&#xff0c;我们给出了一个好理解的简单解法&#xff0c;就是用三…...

Rows 行

Goto Data Grid 数据网格 Rows 行...

十个常见的软件测试面试题,拿走不谢

所有面试问题一般建议先总后分的方式来回答&#xff0c;这样可以让面试官感觉逻辑性很强。 1. 自我介绍 之所以让我们自我介绍&#xff0c;其实是面试官想找一些时间来看简历&#xff0c;所以自我介绍不用太长的时间&#xff0c;1-2分 钟即可。 自我介绍一般按以下方式进行介…...

windows 11 配置 kafka 使用SASL SCRAM-SHA-256 认证

1. 下载安装apache-zookeeper-3.9.2 配置 \conf\zoo.cfg # The number of milliseconds of each tick tickTime2000 # The number of ticks that the initial # synchronization phase can take initLimit10 # The number of ticks that can pass between # sending a requ…...

Elasticsearch —— ES 环境搭建、概念、基本操作、文档操作、SpringBoot继承ES

文章中会用到的文件&#xff0c;如果官网下不了可以在这下 链接: https://pan.baidu.com/s/1SeRdqLo0E0CmaVJdoZs_nQ?pwdxr76 提取码: xr76 一、 ES 环境搭建 注&#xff1a;环境搭建过程中的命令窗口不能关闭&#xff0c;关闭了服务就会关闭&#xff08;除了修改设置后重启的…...

ElSelect 组件的 onChange 和 onInput 事件的区别

偶然遇到一个问题&#xff0c;在 ElSelect 组件中设置 filterable 属性后&#xff0c;监测不到复制粘贴的内容&#xff0c;也就意味着不能调用接口&#xff0c;下拉框内容为空。 简要代码如下&#xff1a; <ElSelectstyle"width: 256px"multiplev-model{siteIdL…...

加密与数据提取:保护隐私的新途径

加密与数据提取&#xff1a;保护隐私的新途径 在数字化时代&#xff0c;数据已成为驱动社会进步和经济发展的关键要素。然而&#xff0c;随着数据量的爆炸性增长&#xff0c;个人隐私保护成为了一个亟待解决的问题。如何在利用数据价值的同时&#xff0c;确保个人隐私不被侵犯…...

博客摘录「 宋宝华:Linux文件读写(BIO)波澜壮阔的一生」2024年11月1日

同时内核会给第2页标识一个PageReadahead标记&#xff0c;意思就是如果app接着读第2页&#xff0c;就可以预判app在做顺序读&#xff0c;这样我们在app读第2页的时候&#xff0c;内核可以进一步异步预读。 每个bio对应的硬盘里面一块连续的位置&#xff0c;每一块硬盘里面连续…...

使用华为云数字人可以做什么

在数字化和智能化快速发展的今天&#xff0c;企业面临着如何提升客户体验、优化运营效率的挑战。华为云数字人作为一种创新的智能交互解决方案&#xff0c;为企业提供了全新的可能性&#xff0c;助力企业在各个领域实现智能化升级。 提升客户服务体验 华为云数字人能够模拟真…...

leetcode刷题记录——(十六)349. 两个数组的交集

&#xff08;一&#xff09;问题描述 . - 力扣&#xff08;LeetCode&#xff09;. - 备战技术面试&#xff1f;力扣提供海量技术面试资源&#xff0c;帮助你高效提升编程技能,轻松拿下世界 IT 名企 Dream Offer。https://leetcode.cn/problems/intersection-of-two-arrays/ …...

vue3实现规则编辑器

组件用于创建和编辑复杂的条件规则&#xff0c;支持添加、删除条件和子条件&#xff0c;以及选择不同的条件类型。 可实现json数据和页面显示的转换。 代码实现 &#xff1a; index.vue: <template><div class"allany-container"><div class"co…...

【快速上手】pyspark 集群环境下的搭建(Standalone模式)

目录 前言 &#xff1a; 一、spark运行的五种模式 二、 安装步骤 安装前准备 1.第一步&#xff1a;安装python 2.第二步&#xff1a;在bigdata01上安装spark 3.第三步&#xff1a;同步bigdata01中的spark到bigdata02和03上 三、集群启动/关闭 四、打开监控界面验证 前…...

中文NLP地址要素解析【阿里云:天池比赛】

比赛地址&#xff1a;中文NLP地址要素解析 https://tianchi.aliyun.com/notebook/467867?spma2c22.12281976.0.0.654b265fTnW3lu长期赛&#xff1a; 分数:87.7271 排名&#xff1a;长期赛:56&#xff08;本次&#xff09;/6990&#xff08;团体或个人&#xff09;方案&#xf…...

【Axure高保真原型】引导弹窗

今天和大家中分享引导弹窗的原型模板&#xff0c;载入页面后&#xff0c;会显示引导弹窗&#xff0c;适用于引导用户使用页面&#xff0c;点击完成后&#xff0c;会显示下一个引导弹窗&#xff0c;直至最后一个引导弹窗完成后进入首页。具体效果可以点击下方视频观看或打开下方…...

多模态2025:技术路线“神仙打架”,视频生成冲上云霄

文&#xff5c;魏琳华 编&#xff5c;王一粟 一场大会&#xff0c;聚集了中国多模态大模型的“半壁江山”。 智源大会2025为期两天的论坛中&#xff0c;汇集了学界、创业公司和大厂等三方的热门选手&#xff0c;关于多模态的集中讨论达到了前所未有的热度。其中&#xff0c;…...

Linux链表操作全解析

Linux C语言链表深度解析与实战技巧 一、链表基础概念与内核链表优势1.1 为什么使用链表&#xff1f;1.2 Linux 内核链表与用户态链表的区别 二、内核链表结构与宏解析常用宏/函数 三、内核链表的优点四、用户态链表示例五、双向循环链表在内核中的实现优势5.1 插入效率5.2 安全…...

【CSS position 属性】static、relative、fixed、absolute 、sticky详细介绍,多层嵌套定位示例

文章目录 ★ position 的五种类型及基本用法 ★ 一、position 属性概述 二、position 的五种类型详解(初学者版) 1. static(默认值) 2. relative(相对定位) 3. absolute(绝对定位) 4. fixed(固定定位) 5. sticky(粘性定位) 三、定位元素的层级关系(z-i…...

如何理解 IP 数据报中的 TTL?

目录 前言理解 前言 面试灵魂一问&#xff1a;说说对 IP 数据报中 TTL 的理解&#xff1f;我们都知道&#xff0c;IP 数据报由首部和数据两部分组成&#xff0c;首部又分为两部分&#xff1a;固定部分和可变部分&#xff0c;共占 20 字节&#xff0c;而即将讨论的 TTL 就位于首…...

2025季度云服务器排行榜

在全球云服务器市场&#xff0c;各厂商的排名和地位并非一成不变&#xff0c;而是由其独特的优势、战略布局和市场适应性共同决定的。以下是根据2025年市场趋势&#xff0c;对主要云服务器厂商在排行榜中占据重要位置的原因和优势进行深度分析&#xff1a; 一、全球“三巨头”…...

NPOI Excel用OLE对象的形式插入文件附件以及插入图片

static void Main(string[] args) {XlsWithObjData();Console.WriteLine("输出完成"); }static void XlsWithObjData() {// 创建工作簿和单元格,只有HSSFWorkbook,XSSFWorkbook不可以HSSFWorkbook workbook new HSSFWorkbook();HSSFSheet sheet (HSSFSheet)workboo…...

C# 表达式和运算符(求值顺序)

求值顺序 表达式可以由许多嵌套的子表达式构成。子表达式的求值顺序可以使表达式的最终值发生 变化。 例如&#xff0c;已知表达式3*52&#xff0c;依照子表达式的求值顺序&#xff0c;有两种可能的结果&#xff0c;如图9-3所示。 如果乘法先执行&#xff0c;结果是17。如果5…...

FFmpeg:Windows系统小白安装及其使用

一、安装 1.访问官网 Download FFmpeg 2.点击版本目录 3.选择版本点击安装 注意这里选择的是【release buids】&#xff0c;注意左上角标题 例如我安装在目录 F:\FFmpeg 4.解压 5.添加环境变量 把你解压后的bin目录&#xff08;即exe所在文件夹&#xff09;加入系统变量…...

Python竞赛环境搭建全攻略

Python环境搭建竞赛技术文章大纲 竞赛背景与意义 竞赛的目的与价值Python在竞赛中的应用场景环境搭建对竞赛效率的影响 竞赛环境需求分析 常见竞赛类型&#xff08;算法、数据分析、机器学习等&#xff09;不同竞赛对Python版本及库的要求硬件与操作系统的兼容性问题 Pyth…...