动态规划 —— 路径问题-最小路径和
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(团体或个人)方案…...
MPNet:旋转机械轻量化故障诊断模型详解python代码复现
目录 一、问题背景与挑战 二、MPNet核心架构 2.1 多分支特征融合模块(MBFM) 2.2 残差注意力金字塔模块(RAPM) 2.2.1 空间金字塔注意力(SPA) 2.2.2 金字塔残差块(PRBlock) 2.3 分类器设计 三、关键技术突破 3.1 多尺度特征融合 3.2 轻量化设计策略 3.3 抗噪声…...
【入坑系列】TiDB 强制索引在不同库下不生效问题
文章目录 背景SQL 优化情况线上SQL运行情况分析怀疑1:执行计划绑定问题?尝试:SHOW WARNINGS 查看警告探索 TiDB 的 USE_INDEX 写法Hint 不生效问题排查解决参考背景 项目中使用 TiDB 数据库,并对 SQL 进行优化了,添加了强制索引。 UAT 环境已经生效,但 PROD 环境强制索…...
ssc377d修改flash分区大小
1、flash的分区默认分配16M、 / # df -h Filesystem Size Used Available Use% Mounted on /dev/root 1.9M 1.9M 0 100% / /dev/mtdblock4 3.0M...
关于nvm与node.js
1 安装nvm 安装过程中手动修改 nvm的安装路径, 以及修改 通过nvm安装node后正在使用的node的存放目录【这句话可能难以理解,但接着往下看你就了然了】 2 修改nvm中settings.txt文件配置 nvm安装成功后,通常在该文件中会出现以下配置&…...
前端导出带有合并单元格的列表
// 导出async function exportExcel(fileName "共识调整.xlsx") {// 所有数据const exportData await getAllMainData();// 表头内容let fitstTitleList [];const secondTitleList [];allColumns.value.forEach(column > {if (!column.children) {fitstTitleL…...
OpenPrompt 和直接对提示词的嵌入向量进行训练有什么区别
OpenPrompt 和直接对提示词的嵌入向量进行训练有什么区别 直接训练提示词嵌入向量的核心区别 您提到的代码: prompt_embedding = initial_embedding.clone().requires_grad_(True) optimizer = torch.optim.Adam([prompt_embedding...
华为云Flexus+DeepSeek征文|DeepSeek-V3/R1 商用服务开通全流程与本地部署搭建
华为云FlexusDeepSeek征文|DeepSeek-V3/R1 商用服务开通全流程与本地部署搭建 前言 如今大模型其性能出色,华为云 ModelArts Studio_MaaS大模型即服务平台华为云内置了大模型,能助力我们轻松驾驭 DeepSeek-V3/R1,本文中将分享如何…...
【JavaWeb】Docker项目部署
引言 之前学习了Linux操作系统的常见命令,在Linux上安装软件,以及如何在Linux上部署一个单体项目,大多数同学都会有相同的感受,那就是麻烦。 核心体现在三点: 命令太多了,记不住 软件安装包名字复杂&…...
代理篇12|深入理解 Vite中的Proxy接口代理配置
在前端开发中,常常会遇到 跨域请求接口 的情况。为了解决这个问题,Vite 和 Webpack 都提供了 proxy 代理功能,用于将本地开发请求转发到后端服务器。 什么是代理(proxy)? 代理是在开发过程中,前端项目通过开发服务器,将指定的请求“转发”到真实的后端服务器,从而绕…...
短视频矩阵系统文案创作功能开发实践,定制化开发
在短视频行业迅猛发展的当下,企业和个人创作者为了扩大影响力、提升传播效果,纷纷采用短视频矩阵运营策略,同时管理多个平台、多个账号的内容发布。然而,频繁的文案创作需求让运营者疲于应对,如何高效产出高质量文案成…...
