动态规划 —— 路径问题-最小路径和
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(团体或个人)方案…...
SpringBoot-17-MyBatis动态SQL标签之常用标签
文章目录 1 代码1.1 实体User.java1.2 接口UserMapper.java1.3 映射UserMapper.xml1.3.1 标签if1.3.2 标签if和where1.3.3 标签choose和when和otherwise1.4 UserController.java2 常用动态SQL标签2.1 标签set2.1.1 UserMapper.java2.1.2 UserMapper.xml2.1.3 UserController.ja…...
.Net框架,除了EF还有很多很多......
文章目录 1. 引言2. Dapper2.1 概述与设计原理2.2 核心功能与代码示例基本查询多映射查询存储过程调用 2.3 性能优化原理2.4 适用场景 3. NHibernate3.1 概述与架构设计3.2 映射配置示例Fluent映射XML映射 3.3 查询示例HQL查询Criteria APILINQ提供程序 3.4 高级特性3.5 适用场…...
【Java学习笔记】Arrays类
Arrays 类 1. 导入包:import java.util.Arrays 2. 常用方法一览表 方法描述Arrays.toString()返回数组的字符串形式Arrays.sort()排序(自然排序和定制排序)Arrays.binarySearch()通过二分搜索法进行查找(前提:数组是…...
Qt Widget类解析与代码注释
#include "widget.h" #include "ui_widget.h"Widget::Widget(QWidget *parent): QWidget(parent), ui(new Ui::Widget) {ui->setupUi(this); }Widget::~Widget() {delete ui; }//解释这串代码,写上注释 当然可以!这段代码是 Qt …...
(二)TensorRT-LLM | 模型导出(v0.20.0rc3)
0. 概述 上一节 对安装和使用有个基本介绍。根据这个 issue 的描述,后续 TensorRT-LLM 团队可能更专注于更新和维护 pytorch backend。但 tensorrt backend 作为先前一直开发的工作,其中包含了大量可以学习的地方。本文主要看看它导出模型的部分&#x…...
条件运算符
C中的三目运算符(也称条件运算符,英文:ternary operator)是一种简洁的条件选择语句,语法如下: 条件表达式 ? 表达式1 : 表达式2• 如果“条件表达式”为true,则整个表达式的结果为“表达式1”…...
RNN避坑指南:从数学推导到LSTM/GRU工业级部署实战流程
本文较长,建议点赞收藏,以免遗失。更多AI大模型应用开发学习视频及资料,尽在聚客AI学院。 本文全面剖析RNN核心原理,深入讲解梯度消失/爆炸问题,并通过LSTM/GRU结构实现解决方案,提供时间序列预测和文本生成…...
Spring Cloud Gateway 中自定义验证码接口返回 404 的排查与解决
Spring Cloud Gateway 中自定义验证码接口返回 404 的排查与解决 问题背景 在一个基于 Spring Cloud Gateway WebFlux 构建的微服务项目中,新增了一个本地验证码接口 /code,使用函数式路由(RouterFunction)和 Hutool 的 Circle…...
Fabric V2.5 通用溯源系统——增加图片上传与下载功能
fabric-trace项目在发布一年后,部署量已突破1000次,为支持更多场景,现新增支持图片信息上链,本文对图片上传、下载功能代码进行梳理,包含智能合约、后端、前端部分。 一、智能合约修改 为了增加图片信息上链溯源,需要对底层数据结构进行修改,在此对智能合约中的农产品数…...
IP如何挑?2025年海外专线IP如何购买?
你花了时间和预算买了IP,结果IP质量不佳,项目效率低下不说,还可能带来莫名的网络问题,是不是太闹心了?尤其是在面对海外专线IP时,到底怎么才能买到适合自己的呢?所以,挑IP绝对是个技…...
