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

动态规划3、悟到核心

news 来源：原创 2025/7/3 23:38:36

题目引入：

#include <iostream>
#include <queue>
#include <vector>
#include <tuple>
#include <algorithm>
#include <cstring>
using namespace std;// dp[i]考虑前i家店能收获的最大价值
// 面对第i家店铺，你可以选择偷，或者不偷
// 偷的话，i-1家就不能偷int main() {int N;cin >> N;vector<int> V(N + 1);for (int i = 1; i <= N; i++) {cin >> V[i];}if (N == 0) {cout << 0 << endl;return 0;}if (N == 1) {cout << V[1] << endl;return 0;}vector<int> dp(N + 1);dp[1] = V[1];dp[2] = max(V[1], V[2]);for (int i = 3; i <= N; i++) {dp[i] = max(dp[i - 1], dp[i - 2] + V[i]);}cout << dp[N] << endl;return 0;
}

dp的核心：

用子问题的最优解来构建原问题的最优解

1. 最优子结构

这是dp的”根基“

——大问题的最优解，一定可以由子问题的最优解提出

比如：前i家店的最大价值，只跟前i-1和i-2家的最大价值有关

2. 状态设计

这是dp的“语言”

——我该怎么用“状态”表示我解决问题的中间结果？

dp[i]表示“处理到第i家店时的最大价值‘

dp[x][y][fuel]表示走到xy位置，持有fuel汽油时的最小花费

3. 状态转移方程

这是dp的”灵魂表达式“

——状态A是怎么从状态B、C、D...推出来的？

4. 记忆化

记忆化搜索、自底向上的dp表格...

——已经知道结果了，就别再重新算一遍！

#include <iostream>
#include <queue>
#include <vector>
#include <tuple>
#include <algorithm>
#include <cstring>
using namespace std;// 甚，原来是区间dp啊！
int dp[11][11];
bool vis[11][11];string A, B;
int n;int dfs(int l, int r) {if (l > r) return 0;if (vis[l][r]) return dp[1][r]; // 剪枝处理vis[l][r] = true;int i = n - (r - l + 1);int take_left = (int)A[l] * (int)B[i] + dfs(l + 1, r);int take_right = (int)A[r] * (int)B[i] + dfs(l, r - 1);return dp[l][r] = max(take_left, take_right);
}int main() {while (cin >> A >> B) {n = A.size();memset(dp, 0, sizeof(dp));memset(vis, 0, sizeof(vis));cout << dfs(0, n - 1) << endl;}return 0;
}

直接暴力dfs，字符数量少

但是如果字符数量大的话我们就要建dp表格了！

#include <iostream>
#include <queue>
#include <vector>
#include <tuple>
#include <algorithm>
#include <cstring>
using namespace std;// 本题的状态为：dp[l][r] = 从 A[l..r] 与 B 匹配能得到的最大能量int main() {string A, B;while (cin >> A >> B) {int n = A.size();vector<vector<int>> dp(n, vector<int>(n, 0));// 区间长度for (int len = 1; len <= n; len++) {for (int l = 0; l + len <= n; l++) {int r = l + len - 1;int i = n - (r - l + 1);if (l == r) {dp[l][r] = A[l] * B[i];}else {dp[l][r] = max(A[l] * B[i] + dp[l + 1][r],A[r] * B[i] + dp[l][r - 1]);}}}cout << dp[0][n - 1] << endl;}return 0;
}

几乎所有 DP 题目，一开始都可以用 DFS 去建模，而动态规划只是对 DFS 的一种优化，优化掉了“重复子问题”的计算。

🍃第一步：DFS 是怎么来的？

很多问题，我们一开始会有一种“我从起点一路走到底”的直觉，这就很像 DFS —— 沿着一个路径一直走下去。

举个例子：

比如之前那个盗贼问题（不能偷相邻的店）：

我们可以这样思考：

我现在站在第 i 家店门口，我可以选择“偷”或者“不偷”。

那我们就写一个函数：

int dfs(int i) { if (i <= 0) return 0; return max(dfs(i - 1), dfs(i - 2) + V[i]); // 不偷 or 偷 }

你看，这就是标准的 DFS：尝试所有选择。

🌱第二步：DFS 有什么缺点？

它的最大问题就是：

会重复算很多次！！！

比如你在求 dfs(10) 的时候，它会递归去算 dfs(9) 和 dfs(8)，但 dfs(9) 又会去算 dfs(8) 和 dfs(7)，你看：

dfs(8) 被重复算了两次
dfs(7) 被重复算了三次
dfs(6) 被重复算了五次……🌪️

这样效率就很差！

🌟第三步：怎么办？优化它！

于是我们就说：

我干嘛重复算呀！我算过的结果，记下来不就行了吗！

这就有了“记忆化搜索”：

int memo[10001]; // 初始化为 -1 int dfs(int i) { if (i <= 0) return 0; if (memo[i] != -1) return memo[i]; return memo[i] = max(dfs(i - 1), dfs(i - 2) + V[i]); }

这样我们就把DFS + 记忆化结合起来了。

而这个做法，其实就是“动态规划的雏形”。

💡第四步：为什么说 DP 是 DFS 的优化？

我们刚刚不是说了吗？DFS 会重复计算 → 我们记下来 → 效率提高。

那我们更进一步，干脆不要递归了，我直接从底往上推，像搭积木一样一步步算出来。

就变成了“表格式DP”：

dp[0] = 0; dp[1] = V[1]; dp[2] = max(V[1], V[2]); for (int i = 3; i <= N; i++) { dp[i] = max(dp[i - 1], dp[i - 2] + V[i]); }

是不是完全和刚才 DFS 的逻辑一样？

只是——不再递归、不再走回头路、效率变得超高✨

动态规划3、悟到核心

题目引入： #include <iostream> #include <queue> #include <vector> #include <tuple> #include <algorithm> #include <cstring> using namespace std;// dp[i]考虑前i家店能收获的最大价值 // 面对第i家店铺，你可…...

编程日记 2025/7/3 23:38:36

VLM-MPC：自动驾驶中模型预测控制器增强视觉-语言模型

《VLM-MPC: Model Predictive Controller Augmented Vision Language Model for Autonomous Driving》2024年8月发表，来自威斯康星大学的论文。受视觉语言模型（VLM）的紧急推理能力及其提高自动驾驶系统可理解性的潜力的启发，本文…...

编程日记 2025/6/27 23:12:24

HTTP/HTTPS 协议浅解

文章目录一、HTTP 协议（一）定义（二）特点（三）应用场景（四）优势（五）劣势二、HTTPS 协议（一）定义（二）特点&…...

编程日记 2025/7/1 18:46:42

Ajax快速入门教程

输入java时，页面并没有刷新但是下面自动联想出了跟java有关的东西，像这种就叫异步交互它不会妨碍你的输入，同时还能够同步进行对于java相关联想词的推送发送异步请求需要借助工具axios 引入axios，可以直接在scripts中引入 get和…...

编程日记 2025/6/27 23:18:44

如何在Java中处理PDF文档（教程）

在开发文档管理系统、自动化工具或商业应用程序时，Java开发者常需处理PDF文档的编辑需求。无论是添加页面、调整内容尺寸、插入水印还是添加注释，选择一套可靠易用的Java PDF开发工具包至关重要。 JPedal（Java PDF开发工具包）的新…...

编程日记 2025/6/27 23:01:15

springcloud集成seata报错Error creating bean with name ‘globalTransactionScanner‘

1. pom文件引入依赖 <dependency><groupId>com.alibaba.cloud</groupId><artifactId>spring-cloud-starter-alibaba-seata</artifactId></dependency> 2. 报错 3. 在启动配置中添加一行配置: --add-opensjava.base/j…...

编程日记 2025/6/27 22:54:37

使用 OpenCV 实现哈哈镜效果：让图像“扭曲起来”！

在计算机视觉和图像处理领域，OpenCV 提供了非常强大的图像几何变换能力，不仅可以用于纠正图像，还能制造各种“有趣”的视觉效果。今天，我们就来实现一个经典的“哈哈镜”效果，让图像像在游乐园里一样被拉伸、压缩、扭曲…...

编程日记 2025/7/2 1:23:37

pikachu靶场暴力破解

学习中参考的博客如下 pikachu靶场暴力破解专题-CSDN博客 1，基于表单的暴力破解出现了一个登录页面解题步骤：抓包，发到bp里，右键发到Intruder，因为有两个位置要爆破，所以选择集群炸弹攻击&#xff…...

编程日记 2025/6/30 16:42:25

鸿蒙开发：应用上架第三篇，配置签名信息打出上架包

前言本文基于Api13 经过前面两篇文章，我们获取到了密钥和证书请求文件以及最终的发布证书和发布证书Profile文件，可以说，所有的签名信息文件，我们都已经完成了，正所谓，万事俱备只欠东风，这篇文…...

编程日记 2025/6/27 23:39:55

基于R语言的贝叶斯网络模型实践技术应用：开启科研新视角

在现代科研领域，变量间的因果关系推断是生态学、环境科学、医学等多学科研究的核心问题。然而，传统的统计学方法往往只能揭示变量间的相关关系，而非因果关系。贝叶斯网络作为一种结合图论与统计学理论的新型模型，不仅能够统合多种…...

编程日记 2025/7/1 15:58:33

第五章 GPT模块配置

由于GPT配置需要和Irq和Mcu进行配合设置（GPT可以由芯片外设中的GTM和GPT12实现，这次是以GTM为实现）。 1 GTM外设时钟配置首先需要对MCU组件进行配置，配置GTM的时钟,需要参照GTM的CMU时钟树。下图时钟树的CLS0_CLK为MCU(McuClockSettingConfig_0中的 McuSTMFrequency )f…...

编程日记 2025/7/2 12:35:50

虚拟机NAT模式获取不到ip

虚拟机NAT模式获取不到ip 如图所示解决方案： 先查看NetworkManager是否启动 systemctl status NetworkManager如果没启动就启动一遍使用DHCP手动获取一遍ip sudo dhclient ens33成功得到ip 这是后遇到了另一个问题，ip释放后，不能自动…...

编程日记 2025/7/3 11:05:28

Docker的网络介绍

网络简单介绍在介绍 Docker 的网络模式之前，先简单说下我们在使用 Vmware 虚拟机中的网络模式，形成对比，更好理解。 1、Vmware 中的网络模式 1.1、VMnet0（桥接模式） 虚拟机通过宿主机的物理网卡直接连接到外部网络…...

编程日记 2025/7/3 11:05:49

Nginx负载均衡配置详解

在Nginx中配置负载均衡主要通过 upstream 模块实现，结合反向代理将请求分发到多个后端服务器。以下是详细配置步骤和案例解析：一、基础配置 1. 配置语法 http {upstream backend_servers {# 负载均衡策略server backend1.example.com;server backend2.example.com;server …...

编程日记 2025/7/3 15:30:57

关于 Web 漏洞原理与利用：4. 文件上传漏洞

定义：文件上传漏洞是指应用程序允许用户上传文件，但没有严格校验上传文件的类型、内容、路径等属性，导致攻击者可以上传并执行恶意代码。绕过方式： 前端绕过 1. 前端限制的原理前端限制上传文件类型的常见方式有三种&#xf…...

编程日记 2025/6/27 23:37:45

(6)python爬虫--selenium

文章目录前言一、初识selenium二、安装selenium2.1 查看chrome版本并禁止chrome自动更新2.1.1 查看chrome版本2.1.2 禁止chrome更新自动更新 2.2 安装对应版本的驱动程序2.3安装selenium包三、selenium关于浏览器的使用3.1 创建浏览器、设置、打开3.2 打开/关闭网页及浏览器3…...

编程日记 2025/6/27 23:18:40

MCU 上电不启动的常见原因分析与排查思路

在开发过程中，“MCU 上电不运行”是我们经常遇到的问题之一。但客户对此类问题的描述往往较为模糊，仅简单表示“产品不工作”或“怀疑 MCU 没有运行”，这给我们现场排查带来了较大的挑战。即便工程师到达现场，往往也无法迅速定位问…...

编程日记 2025/6/29 8:43:20

Spark Core 源码关键环节的深度解析

以下是对 Spark Core 源码关键环节的深度解析，包括核心组件启动与调度机制、Shuffle与调度系统、RDD高级机制。每个环节都细化到具体方法、逻辑、源码片段，附有流程图思路与速记口诀，便于记忆和理解。一、核心组件启动与调度机制 1. RpcEnv…...

编程日记 2025/7/3 19:54:05

net Core》》包与库 LibMan、NPM

LibMan 资料 NPM 资料在 Visual Studio 中使用 npm package.json 保存之后 vs会自动下载的。注意：如果您没有看到 node_modules 文件夹，请确保在 Visual Studio 解决方案资源管理器中启用了“显示所有文件”选项要卸载该库，您只需从 …...

编程日记 2025/6/27 23:21:35

数学建模，机器决策人建模

目录数学建模微分方程动态系统建模时间序列分析概述指数衰减随机漂移总结曲线拟合最优化方法梯度下降法概率建模（如贝叶斯建模、马尔可夫过程、MDP/POMDP） 等贝叶斯建模贝叶斯定理优势马尔可夫过程马尔可夫过程的分类…...

编程日记 2025/6/26 23:20:56

FFmpeg中使用Android Content协议打开文件设备

引言随着Android 10引入的Scoped Storage（分区存储）机制，传统的文件访问方式发生了重大变化。FFmpeg作为强大的多媒体处理工具，也在不断适应Android平台的演进。本文将介绍如何在FFmpeg 7.0版本中使用Android content协议直接访…...

编程日记 2025/7/2 12:16:19

SQL查询, 响应体临时字段报: Unknown column ‘data_json_map‘ in ‘field list‘

Overridepublic AjaxResult list(AgentPageReqVO pageReqVO, Integer pageNo, Integer pageSize) {// 1. 查询数据库获取代理列表List<AgentDO> list agentMapper.selectPage(pageReqVO).getList();// 如果结果为空，直接返回空分页结果if (CollectionUtils.i…...

编程日记 2025/7/1 4:14:57

OpenCv高阶（十四）——LBPH人脸识别

文章目录前言一、LBPH原理1. LBP（局部二值模式）特征提取2. 图像分块处理3. 生成直方图4. 人脸识别（匹配阶段）5. LBPH的特点6. 变种与优化二、LBPH人脸识别简单实现（一）LBPH人脸识别1、图像读取&#xff0…...

编程日记 2025/7/3 4:43:56

C#开发利器：SharpBoxesCore全解析

SharpBoxesCore 是一个基于 C# 的开源开发工具库，旨在为开发者提供一系列常用功能模块和辅助类，以提高开发效率、减少重复代码编写，并增强项目的可维护性和扩展性。该库集成了多种实用工具类和通用扩展方法，适用于桌面应用、Web 项…...

编程日记 2025/7/2 5:02:08

回表是数据库概念，还是mysql的概念？

主键索引没有列，根据耳机索引去查主键索引，又没有查表，为啥叫回表呢？ “回表”这个词，其实算是数据库里的一个通用概念，不过它最常见的应用场景是在 MySQL 的 InnoDB 引擎里，所以很多人一提起回…...

编程日记 2025/7/1 4:21:08

49、c# 能⽤foreach 遍历访问的对象需满足什么条件？

在 C# 中，要使用 foreach 循环遍历一个对象，该对象必须满足以下条件之一： 1. 实现 IEnumerable 或 IEnumerable 接口非泛型版本：System.Collections.IEnumerable public class MyCollection : IEnumerable {private int[] _da…...

编程日记 2025/6/30 6:34:33

DL00987-基于深度学习YOLOv11的红外鸟类目标检测含完整数据集

提升科研能力，精准识别红外鸟类目标！ 完整代码数据集见文末针对科研人员，尤其是研究生们，是否在鸟类目标检测中遇到过数据不够精准、处理困难等问题？现在，我们为你提供一款基于深度学习YOLOv11的红外鸟类…...

编程日记 2025/7/1 20:13:09

07 接口自动化-用例管理框架之pytest单元测试框架

文章目录一、pytest用例管理框架（单元测试框架）二、pytest简介三、pytest的最基本的测试用例的规则四、运行方式1.主函数方式2.命令行方式3.通过pytest.ini的配置文件运行五、pytest 默认执行测试用例的顺序六、跳过测试用例1.无条件跳过 pytest.mark.…...

编程日记 2025/6/27 23:01:16

Flutter 中 build 方法为何写在 StatefulWidget 的 State 类中

Flutter 中 build 方法为何写在 StatefulWidget 的 State 类中在 Flutter 中，build 方法被设计在 StatefulWidget 的 State 类中而非 StatefulWidget 类本身，这种设计基于几个重要的架构原则和实际考量： 1. 核心设计原因 1.1 生命周期管理…...

编程日记 2025/7/2 1:39:57

多技术栈 iOS 项目的性能调试实战：从 Flutter 到 Unity（含 KeyMob 工具实测）

多技术栈 iOS 项目的性能调试实战：从 Flutter 到 Unity 随着移动端开发日趋多元化，iOS 项目中纯 Objective-C/Swift 已不再是唯一选择。越来越多团队采用 Flutter、React Native、Unity、WebView 混合等方案构建 App。这种“技术栈混合”带来灵活性的同…...

编程日记 2025/7/1 14:57:04

Base64加密解密

Base64 是一种基于 64 个可打印字符来表示二进制数据的编码方式，常用于需要通过文本协议传输二进制数据的场景（如 URL、邮件）。以下是不同场景下生成 Base64 编码的方法： 一、编程语言实现 Python import base64# 字符串转Base…...

编程日记 2025/6/27 23:13:53

程序设计基础----排序（2）

1、冒泡排序 #include <stdio.h>#define N 1000 int arr[N];/* 对长度为n的数组arr执行冒泡排序 */ void bubbleSort(int arr[], int n);/* 打印长度为n的数组arr */ void printArray(int arr[], int n);void swap(int *xp, int *yp) {int temp *xp;*xp *yp;*yp temp…...

编程日记 2025/7/3 1:18:54

C++：vector容器

vector容器与array容器相似，但vector容器是动态的，可以自动扩容。使用方法和一些注意如下： #include<iostream> #include<vector> using namespace std;int main() {vector<char> vec { a,b,c,d };vec[4] e;//不能以此…...

编程日记 2025/6/30 4:57:22

十四、Hive 视图 Lateral View

作者：IvanCodes 日期：2025年5月20日专栏：Hive教程在Hive中，我们经常需要以不同于原始表结构的方式查看或处理数据。为了简化复杂查询、提供数据抽象，以及处理复杂数据类型（如数组或Map）&#…...

编程日记 2025/7/3 1:11:54

Frp Dockr Mysql内网映射

用 FRP 远程暴露 Mac mini 上的 Docker-MySQL（含 Ubuntu frps 安装和 macOS 客户端配置） 一、环境说明服务器（公网）：Ubuntu 22.04 frps内网设备：macOS (Mac mini) frpc Docker MySQL目标：…...

编程日记 2025/6/27 23:16:29

PHP 扇形的面积(Area of a Circular Sector)

圆形扇区或圆形扇区是圆盘上由两个半径和一个圆弧围成的部分，其中较小的区域称为小扇区，较大的区域称为大扇区。让我们看看这个图，试着找出扇区： 在该图中，绿色阴影部分是扇形，“r”是半径，“th…...

编程日记 2025/6/30 20:05:57

物业后勤小程序源码介绍

基于ThinkPHPFastAdminUniApp开发的物业后勤小程序源码，它为物业管理提供了高效便捷的解决方案。该源码功能丰富，涵盖房屋认证、家人认证，保障社区居住安全；支持报事报修、装修申请，方便业主与物业沟通；还…...

编程日记 2025/6/29 2:20:53

git基础操作

当远程仓库迁移到一个新的组下面时，你需要在本地仓库中更新远程仓库的URL，以便与新的远程仓库关联。以下是详细步骤： 获取新的远程仓库URL： 首先，你需要从GitLab或相关平台获取新组下的仓库的新URL。通常，仓…...

编程日记 2025/7/1 21:50:24

鸿蒙HarmonyOS 【ArkTS组件】通用属性-背景设置

📑往期推文全新看点（附带最新鸿蒙全栈学习笔记） 嵌入式开发适不适合做鸿蒙南向开发？看完这篇你就了解了~ 鸿蒙岗位需求突增！移动端、PC端、IoT到底该怎么选？ 分享一场鸿蒙开发面试经验记录（三面…...

编程日记 2025/7/1 7:37:32

java 在用redis 的时候，如何合理的处理分页问题？ redis应当如何存储性能最佳

在 Java 中使用 Redis 处理用户表分页时，需结合其数据结构特性优化存储和查询 1. 数据结构设计场景需求用户表字段：id, name, age, register_time（注册时间）分页要求：按注册时间倒序分页展示，每页 10 条…...

编程日记 2025/7/3 19:07:02

分类预测 | Matlab实现PNN概率神经网络多特征分类预测

分类预测 | Matlab实现PNN概率神经网络多特征分类预测目录分类预测 | Matlab实现PNN概率神经网络多特征分类预测分类效果代码功能算法流程程序设计参考资料分类效果代码功能该代码实现了一个基于**概率神经网络（PNN）**的多分类任务，核心功能如下：数据预处理读取Exce…...

编程日记 2025/7/1 16:09:36

spring-retry

学习链接【SpringBoot】spring-retry(重试机制) 【Spring】Spring Retry CSDN有点可恶啊，拿着别人的文章，要开VIP才能看...

编程日记 2025/6/27 21:02:47

RTMP协议解析【二】

文章目录 RTMP协议解析【二】RTMP消息消息的格式Basic HeaderMessage HeaderExtended Timestamp RTMP协议解析【二】本专栏重点负责介绍RTMP协议的理论部分， 跳过定义，协议与其他协议的优缺点对比，协议的拓展与改进，协议的历史发…...

编程日记 2025/7/3 2:55:03

WebGL2混合与雾

混合技术一、混合基本技术混合技术就是将两个片元调和，主要通过各种测试将准备进入帧缓冲（源片元）与帧缓冲中原有片元（目标片元）按照设定的比例加权计算出最终片元的颜色值。两种常用组合 ： 源因子…...

编程日记 2025/7/3 10:51:43

Windows Docker笔记-扩展

docker扩展知识点开放容器端口背景，有一个docker Centos7镜像，运行容器后，想要通过22端口远程这个容器创建容器时开放映射端口，将容器的22端口映射到本地的22端口 docker run -p <宿主机端口>:<容器端口> 镜像名…...

编程日记 2025/7/3 23:25:30

【C++ Primer 学习札记】智能指针

1）std::unique_ptr（独占所有权） 特点： 独占资源的所有权，同一时间只能有一个 unique_ptr 指向特定对象。不可复制，但可以通过 std::move 转移所有权。轻量级，几乎无额外开销（与…...

编程日记 2025/7/3 11:02:51

【嵌入式人工智能产品开发实战】（二十二）—— 政安晨：改造小智AI开发智能体硬件（案例：移植PowerManager后麦克风不工作）

政安晨的个人主页：政安晨欢迎 👍点赞✍评论⭐收藏希望政安晨的博客能够对您有所裨益，如有不足之处，欢迎在评论区提出指正！ 目录确定你硬件的关键点案例分析 🔍 一、关键代码分析 ✅ 1. power_save_…...

编程日记 2025/6/27 23:06:31

Taro Error: chunk common [mini-css-extract-plugin]

目录一、问题描述二、解决方案一、问题描述 taro项目编译时抛出一下异常： Error: chunk common [mini-css-extract-plugin] Conflicting order. Following module has been added: * css ./node_modules/css-loader/dist/cjs.js??ruleSet[1].rules[4].oneOf…...

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

【深度学习】多目标融合算法（六）：渐进式分层提取模型PLE（Progressive Layered Extraction）

目录一、引言二、PLE（Progressive Layered Extraction，渐进式分层提取模型） 2.1 技术原理 2.2 技术优缺点 2.3 业务代码实践 2.3.1 业务场景与建模 2.3.2 模型代码实现 2.3.3 模型训练与推理测试 2.3.4 打印模型结构三、总结一…...

编程日记 2025/7/2 12:38:58

ping、tcpping、psping、paping、hping的区别

ping、tcpping、psping、paping、hping的区别这些工具都是用于网络测试的，但它们在功能和协议上有所不同，适用于不同的场景。 ping 基本功能： 发送ICMP echo请求包，并等待接收echo应答包，从而判断网络是否连通&…...

编程日记 2025/6/29 11:21:08