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

动态规划-----路径问题

动态规划-----路径问题

  • 下降最小路径和
    • 1:状态表示
    • 2:状态转移方程
    • 3 初始化
    • 4 填表顺序
    • 5 返回值
    • 6 代码实现
  • 总结:

下降最小路径和

在这里插入图片描述

1:状态表示

假设:用dp[i][j]表示:到达[i,j]的最小路径

2:状态转移方程

结合图片分析:

在这里插入图片描述

如果图中的A点要到达三角形,那么就会考虑下A点上面的数通过最小路径到达A。
那么通过路径变为 x->A->三角形:

那么我们如何找到到达A点的下降路径呢
由状态表示:用dp[i][j]表示:到达[i,j]的最小路径。
则我们可以转换我到达A点的最小路径为dp[i-1][j-1]或dp[i-1][j]或dp[i-1][j+1]

在这里插入图片描述

在这里插入图片描述

文字总结:在dp表中每一个位置向下都有3种情况,根据这三种情况可以规划处动态方程:
因为要最小路径和,那么我们就可以在三个路径下取最小的路径,这就要用到min
dp[i][j]=  min(dp[i-1][j-1],min(dp[i][j-1],dp[i][j+1]))+d[i][j]----------状态转移方程

3 初始化

初始化的目的是防止越界访问的问题

由状态转移方程得出:dp[i][j]=  min(dp[i-1][j-1],min(dp[i][j-1],dp[i][j+1]))+d[i][j]

由状态转移方程可以得出我们需要上方的3个元素分别是:
[i,j-1]、[i,j]、[i,j+1]

所以我们需要添加1行2列:去避免数组越界的问题(圈圆圈的就是会越界的地方)
在这里插入图片描述
【注意事项】
1:虚线里面的值是要保证不影响后面的操作第一行就不要影响圆圈的值就可以把第一行初始化成0
对于列:不要影响最小值的比对:min(x,y,z)那么把列初始化为正无穷大

在这里插入图片描述

2:d表对应dp表下标的映射

4 填表顺序

填表顺序:从下往上(因为是对于填表左右对状态方程没有什么影响,而上下是有影响的)

5 返回值

返回最后一列的最小值

6 代码实现

class Solution {
public:int minFallingPathSum(vector<vector<int>>& matrix) {//创建dp表int m=matrix.size();int n=matrix[0].size();vector<vector<int>> dp(m+1,vector<int>((n+2),INT_MAX));for(int i=0;i<n+2;i++)//初始化dp[0][i]=0;//填表for(int i=1;i<=m;i++)for(int j=1;j<=n;j++)dp[i][j]=min(dp[i-1][j],min(dp[i-1][j-1],dp[i-1][j+1]))+matrix[i-1][j-1];//返回结果int ret=INT_MAX;for(int i=1;i<=n;i++)ret=min(ret,dp[n][i]);return ret;}
};

总结:

对于路径问题:
第一:分析状态
第二:列出状态方程
第三:初始化(防止越界访问)
第四:填表顺序(由状态方程的出填表顺序)
第五:得出返回值

相关文章:

动态规划-----路径问题

动态规划-----路径问题 下降最小路径和1&#xff1a;状态表示2&#xff1a;状态转移方程3 初始化4 填表顺序5 返回值6 代码实现 总结&#xff1a; 下降最小路径和 1&#xff1a;状态表示 假设&#xff1a;用dp[i][j]表示&#xff1a;到达[i,j]的最小路径 2&#xff1a;状态转…...

Rust循环引用与多线程并发

循环引用与自引用 循环引用的概念 循环引用指的是两个或多个对象之间相互持有对方的引用。在 Rust 中&#xff0c;由于所有权和生命周期的严格约束&#xff0c;直接创建循环引用通常会导致编译失败。例如&#xff1a; // 错误的循环引用示例 struct Node {next: Option<B…...

东方隐侠网安瞭望台第8期

谷歌应用商店贷款应用中的 SpyLoan 恶意软件影响 800 万安卓用户 迈克菲实验室的新研究发现&#xff0c;谷歌应用商店中有十多个恶意安卓应用被下载量总计超过 800 万次&#xff0c;这些应用包含名为 SpyLoan 的恶意软件。安全研究员费尔南多・鲁伊斯上周发布的分析报告称&…...

底部导航栏新增功能按键

场景需求&#xff1a; 在底部导航栏添加power案件&#xff0c;单击息屏&#xff0c;长按 关机 如下实现图 借此需求&#xff0c;需要掌握技能&#xff1a; 底部导航栏如何实现新增、修改、删除底部导航栏流程对底部导航栏部分样式如何修改。 比如放不下、顺序排列、坑点如…...

C++ 之弦上舞:string 类与多样字符串操作的优雅旋律

string 类的重要性及与 C 语言字符串对比 在 C 语言中&#xff0c;字符串是以 \0 结尾的字符集合&#xff0c;操作字符串需借助 C 标准库的 str 系列函数&#xff0c;但这些函数与字符串分离&#xff0c;不符合 OOP 思想&#xff0c;且底层空间管理易出错。而在 C 中&#xff0…...

centos8:Could not resolve host: mirrorlist.centos.org

【1】错误消息&#xff1a; [rootcentos211 redis-7.0.15]# yum update CentOS Stream 8 - AppStream …...

Linux 定时任务 命令解释 定时任务格式详解

目录 时间命令 修改时间和日期 定时任务格式 定时任务执行 查看定时任务进程 重启定时任务 时间命令 #查看时间 [rootlocalhost ~]# date 2021年 07月 23日 星期五 14:38:19 CST --------------------------------------- [rootlocalhost ~]# date %F 2021-07-23 -----…...

aws(学习笔记第十五课) 如何从灾难中恢复(recover)

aws(学习笔记第十五课) 如何从灾难中恢复 学习内容&#xff1a; 使用CloudWatch对服务器进行监视与恢复区域(region)&#xff0c;可用区(available zone)和子网(subnet)使用自动扩展(AutoScalingGroup) 1. 使用CloudWatch对服务器进行监视与恢复 整体架构 这里模拟Jenkins Se…...

github webhooks 实现网站自动更新

本文目录 Github Webhooks 介绍Webhooks 工作原理配置与验证应用云服务器通过 Webhook 自动部署网站实现复制私钥编写 webhook 接口Github 仓库配置 webhook以服务的形式运行 app.py Github Webhooks 介绍 Webhooks是GitHub提供的一种通知方式&#xff0c;当GitHub上发生特定事…...

【C语言】递归的内存占用过程

递归 递归是函数调用自身的一种编程技术。在C语言中&#xff0c;递归的实现会占用内存栈&#xff08;Call Stack&#xff09;&#xff0c;每次递归调用都会在栈上分配一个新的 “栈帧&#xff08;Stack Frame&#xff09;”&#xff0c;用于存储本次调用的函数局部变量、返回地…...

365天深度学习训练营-第P6周:VGG-16算法-Pytorch实现人脸识别

&#x1f368; 本文为&#x1f517;365天深度学习训练营中的学习记录博客&#x1f356; 原作者&#xff1a;K同学啊 文为「365天深度学习训练营」内部文章 参考本文所写记录性文章&#xff0c;请在文章开头带上「&#x1f449;声明」 &#x1f37a;要求&#xff1a; 保存训练过…...

企业AI助理在数据分析与决策中扮演的角色

在当今这个数据驱动的时代&#xff0c;企业每天都需要处理和分析大量的数据&#xff0c;以支持其业务决策。然而&#xff0c;面对如此庞大的数据量&#xff0c;传统的数据分析方法已经显得力不从心。幸运的是&#xff0c;随着人工智能&#xff08;AI&#xff09;技术的不断发展…...

洛谷 B2029:大象喝水 ← 圆柱体体积

【题目来源】https://www.luogu.com.cn/problem/B2029【题目描述】 一只大象口渴了&#xff0c;要喝 20 升水才能解渴&#xff0c;但现在只有一个深 h 厘米&#xff0c;底面半径为 r 厘米的小圆桶 &#xff08;h 和 r 都是整数&#xff09;。问大象至少要喝多少桶水才会解渴。 …...

go每日一题:mock打桩、defer、recovery、panic的调用顺序

题目一&#xff1a;单元测试中使用—打桩 打桩概念&#xff1a;使用A替换 原函数B&#xff0c;那么A就是打桩函数打桩原理&#xff1a;运行时&#xff0c;通过一个包&#xff0c;将内存中函数的地址替换为桩函数的地址打桩操作&#xff1a;利用Patch&#xff08;&#xff09;函…...

STM32F103 HSE时钟倍频以及设置频率函数(新手向,本人也是新手)

HSE_SetSysCLK是野火教程里的,不懂的去这 16-RCC&#xff08;第3节&#xff09;使用HSE配置系统时钟并使用MCO输出监控系统时钟_哔哩哔哩_bilibili HSE_AutoSetHSE的算法部分是自己写的,用了一个转接数组。C语言不支持bool所以自己定义了一个boolK代替bool。 AutoHSE.h: /**…...

renderExtraFooter 添加本周,本月,本年

在 Ant Design Vue 中&#xff0c;a-date-picker 组件提供了一个 renderExtraFooter 属性&#xff0c;可以用来渲染额外的页脚内容。你可以利用这个属性来添加“本周”、“本月”和“本年”的按钮。下面是如何在 Vue 2 项目中实现这一功能的具体步骤&#xff1a; 1.确保安装了…...

SprinBoot整合KafKa的使用(详解)

前言 1. 高吞吐量&#xff08;High Throughput&#xff09; Kafka 设计的一个核心特性是高吞吐量。它能够每秒处理百万级别的消息&#xff0c;适合需要高频次、低延迟消息传递的场景。即使在大规模分布式环境下&#xff0c;它也能保持很高的吞吐量和性能&#xff0c;支持低延…...

【机器学习】CatBoost 模型实践:回归与分类的全流程解析

一. 引言 本篇博客首发于掘金 https://juejin.cn/post/7441027173430018067。 PS&#xff1a;转载自己的文章也算原创吧。 在机器学习领域&#xff0c;CatBoost 是一款强大的梯度提升框架&#xff0c;特别适合处理带有类别特征的数据。本篇博客以脱敏后的保险数据集为例&#x…...

PyTorch 实现动态输入

使用 PyTorch 实现动态输入&#xff1a;支持训练和推理输入维度不一致的 CNN 和 LSTM/GRU 模型 在深度学习中&#xff0c;处理不同大小的输入数据是一个常见的挑战。许多实际应用需要模型能够灵活地处理可变长度的输入。本文将介绍如何使用 PyTorch 实现支持动态输入的 CNN 和…...

【Linux相关】查看conda路径和conda和cudnn版本、安装cudnn、cuDNN无需登录官方下载链接

【Linux相关】 查看conda路径和conda和cudnn版本 安装cudnn cuDNN无需登录官方下载链接 文章目录 1. 查看信息1.1 查看 Conda 路径1.2 查看 Conda 版本1.3 查看 cuDNN 版本1.4 总结 2. 安装cudnn2.1 安装cudnn步骤2.2 cuDNN无需登录官方下载链接 1. 查看信息 查看Conda 路径、C…...

云启出海,智联未来|阿里云网络「企业出海」系列客户沙龙上海站圆满落地

借阿里云中企出海大会的东风&#xff0c;以**「云启出海&#xff0c;智联未来&#xff5c;打造安全可靠的出海云网络引擎」为主题的阿里云企业出海客户沙龙云网络&安全专场于5.28日下午在上海顺利举办&#xff0c;现场吸引了来自携程、小红书、米哈游、哔哩哔哩、波克城市、…...

可靠性+灵活性:电力载波技术在楼宇自控中的核心价值

可靠性灵活性&#xff1a;电力载波技术在楼宇自控中的核心价值 在智能楼宇的自动化控制中&#xff0c;电力载波技术&#xff08;PLC&#xff09;凭借其独特的优势&#xff0c;正成为构建高效、稳定、灵活系统的核心解决方案。它利用现有电力线路传输数据&#xff0c;无需额外布…...

Psychopy音频的使用

Psychopy音频的使用 本文主要解决以下问题&#xff1a; 指定音频引擎与设备&#xff1b;播放音频文件 本文所使用的环境&#xff1a; Python3.10 numpy2.2.6 psychopy2025.1.1 psychtoolbox3.0.19.14 一、音频配置 Psychopy文档链接为Sound - for audio playback — Psy…...

关于 WASM:1. WASM 基础原理

一、WASM 简介 1.1 WebAssembly 是什么&#xff1f; WebAssembly&#xff08;WASM&#xff09; 是一种能在现代浏览器中高效运行的二进制指令格式&#xff0c;它不是传统的编程语言&#xff0c;而是一种 低级字节码格式&#xff0c;可由高级语言&#xff08;如 C、C、Rust&am…...

QT: `long long` 类型转换为 `QString` 2025.6.5

在 Qt 中&#xff0c;将 long long 类型转换为 QString 可以通过以下两种常用方法实现&#xff1a; 方法 1&#xff1a;使用 QString::number() 直接调用 QString 的静态方法 number()&#xff0c;将数值转换为字符串&#xff1a; long long value 1234567890123456789LL; …...

Java面试专项一-准备篇

一、企业简历筛选规则 一般企业的简历筛选流程&#xff1a;首先由HR先筛选一部分简历后&#xff0c;在将简历给到对应的项目负责人后再进行下一步的操作。 HR如何筛选简历 例如&#xff1a;Boss直聘&#xff08;招聘方平台&#xff09; 直接按照条件进行筛选 例如&#xff1a…...

Python Ovito统计金刚石结构数量

大家好,我是小马老师。 本文介绍python ovito方法统计金刚石结构的方法。 Ovito Identify diamond structure命令可以识别和统计金刚石结构,但是无法直接输出结构的变化情况。 本文使用python调用ovito包的方法,可以持续统计各步的金刚石结构,具体代码如下: from ovito…...

Kubernetes 网络模型深度解析:Pod IP 与 Service 的负载均衡机制,Service到底是什么?

Pod IP 的本质与特性 Pod IP 的定位 纯端点地址&#xff1a;Pod IP 是分配给 Pod 网络命名空间的真实 IP 地址&#xff08;如 10.244.1.2&#xff09;无特殊名称&#xff1a;在 Kubernetes 中&#xff0c;它通常被称为 “Pod IP” 或 “容器 IP”生命周期&#xff1a;与 Pod …...

c# 局部函数 定义、功能与示例

C# 局部函数&#xff1a;定义、功能与示例 1. 定义与功能 局部函数&#xff08;Local Function&#xff09;是嵌套在另一个方法内部的私有方法&#xff0c;仅在包含它的方法内可见。 • 作用&#xff1a;封装仅用于当前方法的逻辑&#xff0c;避免污染类作用域&#xff0c;提升…...

JDK 17 序列化是怎么回事

如何序列化&#xff1f;其实很简单&#xff0c;就是根据每个类型&#xff0c;用工厂类调用。逐个完成。 没什么漂亮的代码&#xff0c;只有有效、稳定的代码。 代码中调用toJson toJson 代码 mapper.writeValueAsString ObjectMapper DefaultSerializerProvider 一堆实…...