动态规划 —— 路径问题-最小路径和
1. 最小路径和
题目链接:
64. 最小路径和 - 力扣(LeetCode)
https://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. 最小路径和 题目链接: 64. 最小路径和 - 力扣(LeetCode)https://leetcode.cn/problems/minimum-path-sum/description/ 2. 算法原理 状态表示:以莫一个位置位置为结尾 dp[i,j]表示:到达[i,j…...
《链表篇》---删除链表的倒数第N个节点(中等)
题目传送门 方法一:计算链表长度(迭代) 1.计算链表长度,并且定义哑节点链接链表。 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应用安全的信息泄露的知识,今天跟大家分享点。 robots.txt泄漏敏感信息 漏洞描述:搜索引擎可以通过robots文件可以获知哪些页面可以爬取,哪些页面不可以爬取。Robots协议是网站国际互联网界通行的道德规范,…...
大数据治理:策略、技术与挑战
随着信息技术的飞速发展,大数据已经成为现代企业运营和决策的重要基础。然而,大数据的复杂性、多样性和规模性给数据管理带来了前所未有的挑战。因此,大数据治理应运而生,成为确保数据质量、合规性、安全性和可用性的关键手段。本…...
vscode插件-08 Golang
文章目录 Go安装其他必须软件 Go Go语言环境,只需安装这一个插件。然后通过vscode命令下载安装其他go环境需要的内容。 程序调试,需要创建.vscode文件夹并编写launch.json文件。 安装其他必须软件 ctrlshiftp,调出命令面板,输入…...
数据结构+算法分析与设计[15-18真题版]
2015年考试试题 一、给出数组A[3..8,2..6]0F integer,当它在内存中按行存放和按列存放时,分别写出元素A[i,j]的地址计算公式(设每个元素占两个存储单元)。(10分) 二、已知一棵二叉树的中序序列的结果是BDCEAFHG,后序序列的结果是DECBHGFA,试画出这棵二叉树。(10分…...
单链表OJ题(2):反转链表(三指针法)、找中间节点(快慢指针)
目录 1.反转链表 反转链表总结: 2.链表的中间节点(快慢指针法) 快慢指针法总结 1.反转链表 在这道题中,我们需要把一个单链表反转它们的指向,这里,我们给出了一个好理解的简单解法,就是用三…...
Rows 行
Goto Data Grid 数据网格 Rows 行...
十个常见的软件测试面试题,拿走不谢
所有面试问题一般建议先总后分的方式来回答,这样可以让面试官感觉逻辑性很强。 1. 自我介绍 之所以让我们自我介绍,其实是面试官想找一些时间来看简历,所以自我介绍不用太长的时间,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
文章中会用到的文件,如果官网下不了可以在这下 链接: https://pan.baidu.com/s/1SeRdqLo0E0CmaVJdoZs_nQ?pwdxr76 提取码: xr76 一、 ES 环境搭建 注:环境搭建过程中的命令窗口不能关闭,关闭了服务就会关闭(除了修改设置后重启的…...
ElSelect 组件的 onChange 和 onInput 事件的区别
偶然遇到一个问题,在 ElSelect 组件中设置 filterable 属性后,监测不到复制粘贴的内容,也就意味着不能调用接口,下拉框内容为空。 简要代码如下: <ElSelectstyle"width: 256px"multiplev-model{siteIdL…...
加密与数据提取:保护隐私的新途径
加密与数据提取:保护隐私的新途径 在数字化时代,数据已成为驱动社会进步和经济发展的关键要素。然而,随着数据量的爆炸性增长,个人隐私保护成为了一个亟待解决的问题。如何在利用数据价值的同时,确保个人隐私不被侵犯…...
博客摘录「 宋宝华:Linux文件读写(BIO)波澜壮阔的一生」2024年11月1日
同时内核会给第2页标识一个PageReadahead标记,意思就是如果app接着读第2页,就可以预判app在做顺序读,这样我们在app读第2页的时候,内核可以进一步异步预读。 每个bio对应的硬盘里面一块连续的位置,每一块硬盘里面连续…...
使用华为云数字人可以做什么
在数字化和智能化快速发展的今天,企业面临着如何提升客户体验、优化运营效率的挑战。华为云数字人作为一种创新的智能交互解决方案,为企业提供了全新的可能性,助力企业在各个领域实现智能化升级。 提升客户服务体验 华为云数字人能够模拟真…...
leetcode刷题记录——(十六)349. 两个数组的交集
(一)问题描述 . - 力扣(LeetCode). - 备战技术面试?力扣提供海量技术面试资源,帮助你高效提升编程技能,轻松拿下世界 IT 名企 Dream Offer。https://leetcode.cn/problems/intersection-of-two-arrays/ …...
vue3实现规则编辑器
组件用于创建和编辑复杂的条件规则,支持添加、删除条件和子条件,以及选择不同的条件类型。 可实现json数据和页面显示的转换。 代码实现 : index.vue: <template><div class"allany-container"><div class"co…...
【快速上手】pyspark 集群环境下的搭建(Standalone模式)
目录 前言 : 一、spark运行的五种模式 二、 安装步骤 安装前准备 1.第一步:安装python 2.第二步:在bigdata01上安装spark 3.第三步:同步bigdata01中的spark到bigdata02和03上 三、集群启动/关闭 四、打开监控界面验证 前…...
中文NLP地址要素解析【阿里云:天池比赛】
比赛地址:中文NLP地址要素解析 https://tianchi.aliyun.com/notebook/467867?spma2c22.12281976.0.0.654b265fTnW3lu长期赛: 分数:87.7271 排名:长期赛:56(本次)/6990(团体或个人)方案…...
内存分配函数malloc kmalloc vmalloc
内存分配函数malloc kmalloc vmalloc malloc实现步骤: 1)请求大小调整:首先,malloc 需要调整用户请求的大小,以适应内部数据结构(例如,可能需要存储额外的元数据)。通常,这包括对齐调整,确保分配的内存地址满足特定硬件要求(如对齐到8字节或16字节边界)。 2)空闲…...
Linux链表操作全解析
Linux C语言链表深度解析与实战技巧 一、链表基础概念与内核链表优势1.1 为什么使用链表?1.2 Linux 内核链表与用户态链表的区别 二、内核链表结构与宏解析常用宏/函数 三、内核链表的优点四、用户态链表示例五、双向循环链表在内核中的实现优势5.1 插入效率5.2 安全…...
UDP(Echoserver)
网络命令 Ping 命令 检测网络是否连通 使用方法: ping -c 次数 网址ping -c 3 www.baidu.comnetstat 命令 netstat 是一个用来查看网络状态的重要工具. 语法:netstat [选项] 功能:查看网络状态 常用选项: n 拒绝显示别名&#…...
使用van-uploader 的UI组件,结合vue2如何实现图片上传组件的封装
以下是基于 vant-ui(适配 Vue2 版本 )实现截图中照片上传预览、删除功能,并封装成可复用组件的完整代码,包含样式和逻辑实现,可直接在 Vue2 项目中使用: 1. 封装的图片上传组件 ImageUploader.vue <te…...
【Linux手册】探秘系统世界:从用户交互到硬件底层的全链路工作之旅
目录 前言 操作系统与驱动程序 是什么,为什么 怎么做 system call 用户操作接口 总结 前言 日常生活中,我们在使用电子设备时,我们所输入执行的每一条指令最终大多都会作用到硬件上,比如下载一款软件最终会下载到硬盘上&am…...
【堆垛策略】设计方法
堆垛策略的设计是积木堆叠系统的核心,直接影响堆叠的稳定性、效率和容错能力。以下是分层次的堆垛策略设计方法,涵盖基础规则、优化算法和容错机制: 1. 基础堆垛规则 (1) 物理稳定性优先 重心原则: 大尺寸/重量积木在下…...
【UE5 C++】通过文件对话框获取选择文件的路径
目录 效果 步骤 源码 效果 步骤 1. 在“xxx.Build.cs”中添加需要使用的模块 ,这里主要使用“DesktopPlatform”模块 2. 添加后闭UE编辑器,右键点击 .uproject 文件,选择 "Generate Visual Studio project files",重…...
数据库——redis
一、Redis 介绍 1. 概述 Redis(Remote Dictionary Server)是一个开源的、高性能的内存键值数据库系统,具有以下核心特点: 内存存储架构:数据主要存储在内存中,提供微秒级的读写响应 多数据结构支持&…...
MySQL体系架构解析(三):MySQL目录与启动配置全解析
MySQL中的目录和文件 bin目录 在 MySQL 的安装目录下有一个特别重要的 bin 目录,这个目录下存放着许多可执行文件。与其他系统的可执行文件类似,这些可执行文件都是与服务器和客户端程序相关的。 启动MySQL服务器程序 在 UNIX 系统中,用…...
深度解析云存储:概念、架构与应用实践
在数据爆炸式增长的时代,传统本地存储因容量限制、管理复杂等问题,已难以满足企业和个人的需求。云存储凭借灵活扩展、便捷访问等特性,成为数据存储领域的主流解决方案。从个人照片备份到企业核心数据管理,云存储正重塑数据存储与…...
