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

动态规划part01

news 来源：原创 2025/7/12 12:02:59

文章参考来源代码随想录

理论基础

适用范围：

如果某一问题有很多重叠子问题，使用动态规划是最有效的。

与贪心算法的区别：

动态规划中每一个状态一定是由上一个状态推导出来的，这一点就区分于贪心，贪心没有状态推导，而是从局部直接选最优的

状态转移公式（递推公式）是很重要，但动规不仅仅只有递推公式。

动规五部曲：

1.确定dp数组（dp table）以及下标的含义

2.确定递推公式

3.dp数组如何初始化

4.确定遍历顺序

5.举例推导dp数组

debug：

找问题的最好方式就是把dp数组打印出来，看看究竟是不是按照自己思路推导的

以及反思：

这道题目我举例推导状态转移公式了么？
我打印dp数组的日志了么？
打印出来了dp数组和我想的一样么？

509. 斐波那契数

动规五部曲：

1.确定dp数组以及下标的含义：第i个位置的斐波那契值为dp[i]；

2.确定递推公式：dp[i]=dp[i-1]+dp[i-2];

3.dp数组如何初始化:斐波那契数列初始前两个位置为0,1；

4.确定遍历顺序：因为递推是从前往后因此这里从前往后遍历；

5.举例推导dp数组：

按照这个递推公式dp[i] = dp[i - 1] + dp[i - 2]，我们来推导一下，当N为10的时候，dp数组应该是如下的数列：

0 1 1 2 3 5 8 13 21 34 55

class Solution {
public:int fib(int n) {if(n<=1)return n;vector<int>dp(n+1);dp[0]=0;dp[1]=1;for(int i=2;i<=n;i++){dp[i]=dp[i-1]+dp[i-2];}return dp[n];}
};

特别情况：

当n小于等于1时这里不用递归公式，因为这两个本来就有初始化的，所以直接输出即可

优化：

我们只需要维护两个数值就可以了，不需要记录整个序列，因此这里可以用sum来记录dp[i-1]+dp[i-2]的值，然后更新dp[i-2]为dp[i-1]，dp[i-1]为sum。

70. 爬楼梯

动规五部曲：

1.确定dp数组以及下标的含义：能爬到第i个位置的方法为dp[i]；

2.确定递推公式：dp[i]=dp[i-1]+dp[i-2];

3.dp数组如何初始化:前两个台阶能爬的方法初始化为1,2；

4.确定遍历顺序：因为递推是从前往后因此这里从前往后遍历；

5.举例推导dp数组：

当n=3时，应该是第一个台阶方法数+第二个的，结果是1+2=3成立

dp数组0 1 2 3

class Solution {
public:int climbStairs(int n) {if(n==1)return n;vector<int>dp(n+1);dp[1]=1;dp[2]=2;for(int i=3;i<=n;i++){dp[i]=dp[i-1]+dp[i-2];}return dp[n];}
};

特别情况：

当n等于1时这里不用递归公式，因为第一个台阶只有一种方法，所以直接输出即可

优化：

我们只需要维护两个数值就可以了，不需要记录整个序列，因此这里可以用sum来记录dp[i-1]+dp[i-2]的值，然后更新dp[i-2]为dp[i-1]，dp[i-1]为sum。

746. 使用最小花费爬楼梯

动规五部曲：

1.确定dp数组以及下标的含义：能爬到第i个位置并由此向上爬的最小花费为dp[i]（包括该位置的花费，因为这里我们要cost是不包括最后一个台阶的）；

2.确定递推公式： dp[i]=min(dp[i-1],dp[i-2])+cost[i];

3.dp数组如何初始化:能爬到前两个台阶（0,1）并由此向上爬的最小花费初始化为cost[0]，cost[1]；

4.确定遍历顺序：因为递推是从前往后因此这里从前往后遍历；

5.举例推导dp数组：

具体cost具体分析

拿示例2：cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1] ，来模拟一下dp数组的状态变化，如下

需要注意的点：

这里dp大小初始化为cost大小，爬到最后一个台阶的最小花费实际上就是爬到倒数第一个或者第二个台阶并由此向上爬的最小花费

class Solution {
public:int minCostClimbingStairs(vector<int>& cost) {vector<int>dp(cost.size());dp[0]=cost[0];dp[1]=cost[1];for(int i=2;i<cost.size();i++){dp[i]=min(dp[i-1],dp[i-2])+cost[i];}return min(dp[cost.size()-1],dp[cost.size()-2]);}
};

动态规划part01

文章参考来源代码随想录理论基础适用范围： 如果某一问题有很多重叠子问题，使用动态规划是最有效的。与贪心算法的区别： 动态规划中每一个状态一定是由上一个状态推导出来的，这一点就区分于贪心，贪心没有状态推…...

编程日记 2025/7/12 12:02:59

生活大爆炸版石头剪刀布(洛谷P1328)

生活大爆炸版石头剪刀布(洛谷P1328) [NOIP2014 提高组] 前言： 由于洛谷发布题解有限制，所以在CSDN上发布洛谷题解。所有题解均是Java语言, 但是思路是相同的每篇都是刷题日常，尽量讲清楚算法逻辑。希望有问题还请大佬们指导！ …...

编程日记 2025/7/8 19:19:26

【GOOD】DeGEM

ICLR2025 under review 看到不错的想法，学习一下 Decoupled Graph Energy-based Model for Node Out-of-Distribution Detection on Heterophilic Graphs 🐱🐶图上的OOD检测的工作是比较少的，相比于图像数据，图结构数…...

编程日记 2025/7/7 9:17:34

jenkins邮件的配置详解

Jenkins邮件的配置涉及多个步骤和细节，以下是详细的配置指南：一、前期准备确定邮件服务：明确Jenkins将要使用的邮件服务，如QQ邮箱、163邮箱、公司邮箱（基于Microsoft 365或Exchange Server）等。获取SMTP配置信息：根据邮件服务类型，获取相应的SMTP服务器地址、端口号…...

编程日记 2025/7/11 10:23:17

flask-socketio相关总结

flask-socketio是一个为flask应用程序添加的实时双向通信功能的扩展库，有了这个库，就可以在flask应用中应用websocket协议，帮助flask实现低延迟、双向的客户端、服务端通信。客户端通过任何SocketIO官方库，都能与服务器建立长连接…...

编程日记 2025/7/10 19:22:15

每日一题 LCR 097. 不同的子序列

LCR 097. 不同的子序列使用动态规划就可以解决，重点是知道动态规划的状态是如何转移的 class Solution { public:int numDistinct(string s, string t) {int ns s.size();int nt t.size();vector<vector<long>> dp(ns1,vector<long>(nt1,0)…...

编程日记 2025/7/9 16:41:34

合并区间C和C++的区别、布尔、整型、浮点、指针类型和0做比较、malloc、calloc、realloc的区别

56. 合并区间 class Solution { public:vector<vector<int>> merge(vector<vector<int>>& intervals) {//先按照每个区间的左元素排序，这样每个区间的左边界就固定了，所以之后考虑相邻的//区间是否是相交的就行类似与栈的…...

编程日记 2025/7/8 14:22:26

设计模式-外观模式

背景有一个家庭影院，有DVD播放器，投影仪，屏幕，音响，爆米花机，每一个设备都有一个遥控器。传统思路： 创建一个客户端类，在这个类中创建所有设备的相关对象（遥控器&am…...

编程日记 2025/7/6 23:29:04

嵌入式驱动开发详解14（SPI驱动架构实现）

文章目录前言SPI简介SPI介绍SPI工作模式SPI特点驱动开发驱动架构SPI控制器驱动SPI设备驱动SPI 设备和驱动匹配过程SPI其他相关API函数参考文献前言 SPI 是很常用的串行通信协议，可以通过 SPI 来连接众多的传感器，相比 I2C 接口，SPI 接口…...

编程日记 2025/7/11 21:40:19

【保姆级系列：思科模拟器安装下载汉化教程大全】

文章目录概述Packet Tracer下载Packet Tracer安装Packet Tracer使用EVE-NG下载：EVE-NG安装：EVE-NG使用： 概述思科在网络界的地位是众所周知的。如果说在中美科技战中，华为代表CHN，那么思科就代表US，依然…...

编程日记 2025/7/8 18:22:38

2024 一带一路暨金砖国家技能发展与技术创新大赛【网络安全防护治理实战技能赛项】样题（中职组）

2024 一带一路暨金砖国家技能发展与技术创新大赛【网络安全防护治理实战技能赛项】样题（中职组） 1.基础设置和安全强化（xxx 分）1.3. 任务内容: 2.安全监测和预警（xxx 分）2.1. 任务一：建立目录安…...

编程日记 2025/7/9 4:11:38

QT 中基于 TCP 的网络通信

基础基于 TCP 的套接字通信需要用到两个类： 1）QTcpServer：服务器类，用于监听客户端连接以及和客户端建立连接。 2）QTcpSocket：通信的套接字类，客户端、服务器端都需要使用。这两个套接字通信类…...

编程日记 2025/7/8 5:38:19

React Native 速度提升 550%

React Native 爱好者们！🌟 您准备好听一些激动人心的消息了吗？React Native 刚刚发布了其最大的更新之一：一种全新的架构，彻底改变了我们构建移动应用程序的方式。如果您想知道这对您的项目和开发体验意味着什么，请继续关注！我们正在深入探讨这个改变游戏规则的事物；您…...

编程日记 2025/7/6 11:04:18

火语言RPA流程组件介绍--键盘按键

🚩【组件功能】：模拟键盘按键配置预览配置说明按键点击后,在弹出的软键盘上选择需要的按键执行后等待时间(ms) 默认值300,执行该组件后等待300毫秒后执行下一个组件. 输入输出输入类型万能对象类型(System.Object)输出类型万能对象类型…...

编程日记 2025/7/10 20:21:08

数值分析—数值积分

研究背景积分的数学解法为牛顿莱布尼兹公式，数学表示为 ∫ a b f ( x ) d x F ( b ) − F ( a ) \int_{a}^{b} f(x)dxF(b)-F(a) ∫abf(x)dxF(b)−F(a)，但应用该方法有如下困难： 1， f ( x ) f(x) f(x)的原函数有时不能用初等函…...

编程日记 2025/7/10 0:41:18

Next.js优化教程：优化字体加载

更多有关Next.js教程，请查阅： 【目录】Next.js 独立开发系列教程-CSDN博客目录更多有关Next.js教程，请查阅： 前言 1. 字体加载的常见问题 1.1 什么是 FOIT 和 FOUT？ 1.2 字体优化的核心目标 2. Next.js 字体优…...

编程日记 2025/7/8 4:32:09

功能篇：springboot中全局异常

在Java应用程序中实现全局异常处理是确保应用健壮性和用户体验良好性的重要一步。通过全局异常处理，你可以集中管理所有未捕获的异常，并以统一的方式响应它们。对于Web应用程序（如使用Spring框架的应用），通常会创建一个…...

编程日记 2025/7/7 9:19:27

【go 】 select case 的用法

文章目录 1. 基本使用：监听多个通道，会阻塞2.带默认分支：非阻塞操作3. 永远监听多个通道4. 超时机制5. 关闭通道的处理6. context的关闭判断相关文章： 【go】select 语句case的随机性【go】 select case 超时机制(time.After)示…...

编程日记 2025/7/7 23:24:31

出海服务器可以用国内云防护吗

随着企业国际化进程的加速，越来越多的企业选择将业务部署到海外服务器上，以便更贴近国际市场。然而，海外服务器也面临着来自全球各地的安全威胁和网络攻击。当出海服务器遭受攻击时，是否可以借助国内的云服务器来进行有效的防护呢…...

编程日记 2025/7/10 23:38:16

前端权限控制一、路由权限（控制页面访问） vue // router.js const routes [{path: /dashboard,name: Dashboard,component: () > import(/views/Dashboard.vue),meta: { requiresAuth: true, roles: [admin, manager] }},{path: /user,name: Use…...

编程日记 2025/7/8 20:38:44

计算机组成原理（二）：指令跳转

指令跳转（Instruction Jump）是计算机程序控制流的重要组成部分，通过改变程序的执行顺序实现循环、条件分支和函数调用等功能。基本概念跳转指令主要用来修改**程序计数器（Program Counter, PC）**的值，使…...

编程日记 2025/7/10 16:39:24

LoViT: 用于手术阶段识别的长视频Transformer|文献速递-生成式模型与transformer在医学影像中的应用

Title 题目 LoViT: Long Video Transformer for surgical phase recognition LoViT: 用于手术阶段识别的长视频Transformer 01 文献速递介绍快速发展的手术数据科学（SDS）领域旨在通过先进利用手术室（OR）内医疗设备采集的数据…...

编程日记 2025/7/7 20:38:34

【传感器技术】第4章力敏传感器，弹性敏感元件的基本特性，应变式压力传感器，电阻应变片的温度补偿，压阻式压力传感器，压电式压力传感器

关注作者了解更多我的其他CSDN专栏过程控制系统工程测试技术虚拟仪器技术可编程控制器工业现场总线数字图像处理智能控制传感器技术嵌入式系统复变函数与积分变换单片机原理线性代数大学物理热工与工程流体力学数字信号处理光电融合集成电路…...

编程日记 2025/7/13 5:46:36

linux之vim

一、模式转换命令 vim主要有三种模式：命令模式（Normal Mode）、输入模式（Insert Mode）和底线命令模式（Command-Line Mode）。从命令模式切换到输入模式：i：在当前光标所在…...

编程日记 2025/7/10 1:17:27

【LeetCode】每日一题 2024_12_9 判断国际象棋棋盘中一个格子的颜色（找规律）

前言每天和你一起刷 LeetCode 每日一题~ LeetCode 启动！ 题目：判断国际象棋棋盘中一个格子的颜色最近力扣一直在出棋盘类的题目，这个月已经出了 9 天了，我倒要看看他是不是真能出一个月代码与解题思路先读题：题…...

编程日记 2025/7/8 9:48:58

HCL虚拟环境搭建并且支持ssh远程访问

1.连接设备新建设备和host主机，连线，host主机选择本地网卡（不选host-only网卡） 2.启动设备，打开终端，按ctrlc 3.执行命令 <H3C>system-view [H3C]int g0/0 [H3C-GigabitEthernet0/0]ip address …...

编程日记 2025/7/5 1:11:10

批量验证指定漏洞思路和流程

免责申明本文仅是用于学习研究POC的地址收集与漏洞验证原理，请勿用在非法途径上，若将其用于非法目的，所造成的一切后果由您自行承担，产生的一切风险和后果与笔者无关；本文开始前请认真详细学习《‌中华人民共和国网络安全法》【学法时习之丨网络安全在身边一图了解网络安…...

编程日记 2025/7/11 1:06:10

首次打开韦东山提供的Ubuntu-18.04镜像后,该做哪些事？

目录 01-测试有无网络02-配置最基本的嵌入式开发环境(安装tftp-nfs等)03-缩短关机强制结束进行时间04-关闭软件的自动更新05-未完待续... 01-测试有无网络 ping www.baidu.com 02-配置最基本的嵌入式开发环境(安装tftp-nfs等) 需要安装 tftp，nfs，vim …...

编程日记 2025/7/8 1:29:25

怎么才能让图片不能转发截图保存

发私密图片给好友又担心被截图保存甚至转发给第三人？有没有办法让发出去的图片不能转发、截图、保存？当然有！今天教你一招，并且对方打开不需要下载任何软件，发出去对方点开就能看。操作步骤如何发送这样限制截图的图…...

编程日记 2025/7/8 9:51:10

设计模式-装饰器模式(结构型)与责任链模式(行为型)对比，以及链式设计

提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档文章目录前言1.装饰器模式1.1概念1.2作用1.3应用场景1.4特点1.5类与对象关系1.6实现 2责任链模式2.1概念2.2作用2.3应用场景2.4特点2.5类与对象关系2.6实现 3.对比总结前言…...

编程日记 2025/7/10 13:44:44

outlook软件配置邮箱提示“到邮件服务器的加密连接不可用”

outlook软件配置邮箱提示“到邮件服务器的加密连接不可用” 问题描述： outlook软件里邮箱提示“已断开”或配置邮箱时提示“到邮件服务器的加密连接不可用”。解决方案： 一、更改注册表（可先导出备份） winr，输入re…...

编程日记 2025/7/9 18:40:39

通过QT实现进度条随着读取文件增加

mythread循环给主线程发送信号实现主线程循环的功能 widget.h #ifndef WIDGET_H #define WIDGET_H#include <QWidget> #include <QFile> #include <QFileDialog> #include <QTextStream> #include <QByteArray> #include "mythread.h"…...

编程日记 2025/7/12 21:43:17

构建高效可靠的分布式推理系统：深入解析控制器与模型服务的协同工作

在现代互联网应用中，随着用户需求的增长和技术的进步，单一服务器已经难以满足大规模并发请求的需求。为了提升系统的性能和可靠性，开发者们越来越多地采用分布式架构。本文将结合具体的代码示例，深入浅出地探讨如何构建一个高效的分布式推理系统，并详细解析其中的关键组件…...

编程日记 2025/7/9 19:14:26

洛谷B2082

数字统计 - 洛谷数字统计题目描述请统计某个给定范围 [L,R] 的所有整数中，数字 2 出现的次数。比如给定范围 [2,22]，数字2 在数 2 中出现了 1 次，在数 12 中出现 1 次，在数 20中出现 1次，在数 21 中出现 1 次&…...

编程日记 2025/7/8 16:48:13

HTML5系列（14）-- 链接与资源关系指南

前端技术探索系列：HTML5 链接与资源关系指南 🔗 致读者：探索资源加载的艺术 👋 前端开发者们， 今天我们将深入探讨 HTML5 的链接与资源关系管理，学习如何优化网站的资源加载策略，提升用户体验…...

编程日记 2025/7/11 22:05:51

ubuntu系统每天凌晨定时上传redis 备份数据到阿里云OSS上

1.压缩备份脚本 1.1 代码如下#!/bin/bash# redis_backup_compress.sh # 设置变量 BACKUP_DIR"/data/redis/backup" REDIS_DIR"/var/lib/redis" DATE$(date %Y%m%d_%H%M%S) BACKUP_FILE"redis_backup_${DATE}.rdb" COMPRESSED_FILE"redis_b…...

编程日记 2025/7/6 20:10:14

uniapp结合movable-area与movable-view实现拖拽功能

前言因为公司业务开发需要拖拽功能。 ps：该功能只能针对高度一致的，如果高度不一致需要另外二开演示开始 <template><view style"height: 100%;"><movable-area :style"{width: 100%, height: allHeight px}"…...

编程日记 2025/7/11 7:24:48

JavaScript 单例模式的创建与应用

JavaScript 单例模式的创建与应用单例模式（Singleton Pattern）是一种设计模式，旨在确保一个类只有一个实例，并提供全局访问点。在 JavaScript 中，单例模式可以帮助我们避免多次创建同一个对象，节省资源&a…...

编程日记 2025/7/8 17:13:44

【HarmonyOS】鸿蒙保存图片或视频到相册

【HarmonyOS】鸿蒙保存图片或视频到相册前言鸿蒙中保存图片或者视频，或者其他媒体文件到设备的媒体库，可以是相册，也可以是文件管理等。共有两种方式： 需要应用申请受限权限，获取文件读写的权限（调用…...

编程日记 2025/7/8 22:48:07

windows下nacos启动报错：java.lang.unsatisfiedLinkError: C:\USers\乱码AppData\xxx.dll

问题看了许多别的帖子，大家都是因为缺少dll包，下载安装 Microsoft Visual C 2015 Redistributable 就可以。但我试过了不行。思来想去，之前正常的时候用的JDK版本是17，后面别的项目用1.8给切换回来了。然后尝试配置环境变量将JD…...

编程日记 2025/7/10 12:42:20

梳理你的思路(从OOP到架构设计)_基本OOP知识01

目录 1、“-Oriented” 的涵意 2、 ” -Oriented”、” -Based”、” -Driven”、” -Centered” 它们之间区别 3、从对象(Object) 谈起 4、类的用途： 叙述软件对象 Android从程序员到架构师之路：梳理你的思路(从OOP到架构设计) 1、“-Oriented” …...

编程日记 2025/7/12 22:49:06

【C++图论 BFS算法】2467. 树上最大得分和路径|2053

本文涉及知识点 C图论 CBFS算法 LeetCode2467. 树上最大得分和路径一个 n 个节点的无向树，节点编号为 0 到 n - 1 ，树的根结点是 0 号节点。给你一个长度为 n - 1 的二维整数数组 edges ，其中 edges[i] [ai, bi] ，表示节点 a…...

编程日记 2025/7/7 18:47:12

Java的Mvc整合Swagger的knife4框架

Swagger的介绍 Swagger 是一个规范和完整的框架，用于生成、描述、调用和可视化 RESTful 风格的 Web 服务。使用Swagger，就是把相关的信息存储在它定义的描述文件里面（yml或json格式），再通过维护这个描述文件可以去更…...

编程日记 2025/7/6 21:57:28

AI项目二十六：YOLOV11简单部署测试

若该文为原创文章，转载请注明原文出处。一、YOLOv11介绍继YOLOv 8、YOLOv 9和YOLOv10之后，发布的YOLOV11引入了几个突破性的增强功能，为目标检测和计算机视觉设定了新的基准。增强的特征提取：YOLOv11使用改进的主干和颈部架构…...

编程日记 2025/7/8 1:12:18

19. Three.js案例-创建一个带有纹理映射的旋转平面

19. Three.js案例-创建一个带有纹理映射的旋转平面实现效果知识点 WebGLRenderer (WebGL渲染器) WebGLRenderer 是 Three.js 中用于渲染场景的主要类。它利用 WebGL 技术在浏览器中绘制 3D 图形。构造器 new THREE.WebGLRenderer(parameters)参数类型描述parametersobj…...

编程日记 2025/7/13 4:46:34

【Makefile】编译日志之输出重定向符号＞

用法1 make all >& compilelog.txt make all > compilelog.txt这两个编译命令在功能上有一些细微的区别，主要在于标准输出和标准错误的处理方式。 make all >& compilelog.txt 这个命令会将标准输出（stdout）和标准错误&a…...

编程日记 2025/7/7 10:40:39

TDengine 新功能复合主键

1. 简介从 TDengine 3.3.0.0 版本之后，新增了复合主键的功能。 TDengine 原来的时间列是不允许有重复时间戳的，有了复合主键功能后，时间列即允许有重复，重复后的时间戳按紧跟其后第二列主键列的值来确定唯一性。此功能的常用…...

编程日记 2025/7/13 0:13:45

【OpenHarmony】初识设备间互联互通的统一基础：分布式软总线

分布式软总线前言软总线软总线代码目录软总线传输模块概述传输模块主要对外接口和使用方式前言很久没有写出一篇能够分享出来的学习心得了，零零散散地写了好多，总是不太满意。今年8月份开始正式投入精力去学习open harmony，记得第一次接触…...

编程日记 2025/7/8 22:40:42

yocto加软件包install 动态链接库报错

加入bb文件,编译通过在install时报错报错 ERROR: demo-1.0-r0 do_package_qa: QA Issue: -dev package agent-dev contains non-symlink .so ‘/usr/lib64/libdemo.so’ 解决在bb文件install前加2行 SOLIBS ".so" FILES_SOLIBSDEV ""do_install …...

编程日记 2025/7/8 8:17:00

《数据结构》（408代码题）

2009 单链表（双指针） 分析：首先呢，给我们的数据结构是一个带有表头结点的单链表，也不允许我们改变链表的结构。链表的长度不是直接给出的啊，所以这个倒数也很棘手。那我们该如何解决这个“k”呢&#xff0c…...

编程日记 2025/7/8 23:05:10

理论基础

适用范围：

与贪心算法的区别：

动规五部曲：

debug：

509. 斐波那契数

动规五部曲：

特别情况 ：

优化：

70. 爬楼梯

动规五部曲：

特别情况 ：

优化：

746. 使用最小花费爬楼梯

动规五部曲：

需要注意的点 ：

相关文章：

特别情况：

特别情况：

需要注意的点：