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

深入理解动态规划(dp)--(提前要对dfs有了解)

news 来源：原创 2025/7/5 4:37:37

前言：对于动态规划：该算法思维是在dfs基础上演化发展来的，所以我不想讲的是看到一个题怎样直接用动态规划来解决，而是说先用dfs搜索，一步步优化，这个过程叫做动态规划。（该文章教你怎样一步步的解决这类题）

一、动态规划入门

二、跳台阶问题---来自AcWing

1.用暴力搜索dfs来解

2.记忆化搜索实现

3.递推实现

二、大盗阿福---来自AcWing

1.用dfs暴力搜索

2.记忆化搜索

3.递推实现

四、数字三角形---来自洛谷

1.用暴力搜索dfs

2.用记忆化搜索

3.递推dp

一、动态规划入门

动态规划就是：给定一个问题，我们将它拆解为一个个子问题，直到子问题可以直接解决，然后把子问题的答案保存起来，以减少重复计算，再根据子问题答案反推，得出原问题的一种方法

动态规划入门思路：dfs暴力--->记忆化搜索--->递推DP

下面正式开始讲解，还是在题中带大家慢慢理解动态规划的思维

二、跳台阶问题---来自AcWing

一个楼梯共有n级台阶，每次可以走一级或者两级，问从第0级台阶走到第n级台阶一共有多少种方案。

输入格式：

共一行，包含一个整数n

输出格式：

共一行，包含一个整数，表示方案数

数据范围：

1<=n<=15

输入样例：

5

输出样例：

8

1.用暴力搜索dfs来解

这个题大部分同学都应该见过，最初我们用递归来解决这道题，其实本质上也是dfs暴力搜索

#include<iostream>
#include<algorithm>
using namespace std;
int n;
int fib(int x)
{if (x == 1)return 1;else if (x == 2)return 2;else return fib(x - 1) + fib(x - 2);
}
int main(void)
{cin >> n;int res = fib(n);cout << res << endl;return 0;
}

这时我们会发现，当n=41时，时间就快到了1s，所以要想办法去优化代码

2.记忆化搜索实现

这里我拿n=5为例，来画一下搜索树，然后分析一下怎么优化

如果是用一个数组来存储一下的话，直接就省去了这棵大树的右分支，因为左分支中的3已经搜索过了，当以后遇到别的题或者n更大时这棵树的左右分支也会很大，所以省去的搜索也就更多。

#include<iostream>
#include<algorithm>
using namespace std;
int arr[100];
int n;
int fib(int x)
{if(arr[x])return arr[x];int sum=0;if (x == 1) sum=1;else if (x == 2) sum=2;else sum=fib(x-1)+fib(x-2);arr[x]=sum;return sum;
}
int main(void)
{scanf("%d",&n);int res = fib(n);printf("%d\n",res);return 0;
}

直接将900多毫秒优化到了2毫秒。

3.递推实现

递归的过程：“归”的过程才是产生答案的过程

“递”的过程是分解子问题的过程（把大问题分解为子问题）

“递”：自顶向下

“归”：自底向上

而我们自底向上一步步推出答案的过程-----就是递推

好，接下来就用递推的方式进行编程：

#include<iostream>
#include<algorithm>
using namespace std;
int F[100];
int n;
int main(void)
{scanf("%d",&n);F[1]=1,F[2]=2;for(int i=3;i<=n;i++){F[i]=F[i-2]+F[i-1];//这个递推公式也就是dfs的状态转移公式}printf("%d\n",F[n]);return 0;
}

总结：

跳台阶这道题：我们就是这样做的：

最暴力的dfs--->记忆化搜索--->递推（dp）

记忆化搜索=暴力bfs+记录答案

递推的公式=dfs向下递归的公式

递推数组的初始值=递归的边界

二、大盗阿福---来自AcWing

阿福是一名经验丰富的大盗。趁着月黑风高，阿福打算今晚洗劫一条街上的店铺。这条街上一共有 N 家店铺，每家店中都有一些现金。阿福事先调查得知，只有当他同时洗劫了两家相邻的店铺时，街上的报警系统才会启动，然后警察就会蜂拥而至。
作为一向谨慎作案的大盗，阿福不愿意冒着被警察追捕的风险行窃。
他想知道，在不惊动警察的情况下，他今晚最多可以得到多少现金?
输入格式:
输入的第一行是一个整数 T，表示一共有 T 组数据。接下来的每组数据，第一行是一个整数 N ，表示一共有 N 家店铺,第二行是 N 个被空格分开的正整数，表示每一家店铺中的现金数量每家店铺中的现金数量均不超过1000。
输出格式:

对于每组数据，输出一行

该行包含一个整数，表示阿福在不惊动警察的情况下可以得到的现金

范围：

1<=T<=50

1<=N<=1e5

输入样例：

2

3

1 8 2

4

10 7 6 14

输出样例：

8

24

1.用dfs暴力搜索

先画搜索树，这道题是选和不选问题

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1e5 + 10;
int arr[N];
int n, t;
int res = 0;
int dfs(int x)//x表示当前正在考虑哪家店
{if (x > n)return 0;else return max(dfs(x + 1), dfs(x + 2) + arr[x]);
}
int main(void)
{cin >> t;while (t--){cin >> n;for (int i = 1; i <= n; i++)scanf_s("%d", &arr[i]);int res = dfs(1);}return 0;
}

放到官网提交一下答案发现，时间超时，因为dfs的时间复杂度是2的n次方，超时是理所当然的事，还是要想办法优化

2.记忆化搜索

要想实现记忆化搜索的话，那么dfs的参数就需要尽可能的少，不应该把没有影响到边界的参数放进来

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1e5 + 10;
int arr[N];
int mem[N];
int n, t;
int res = 0;
int dfs(int x)//x表示当前正在考虑哪家店
{if (mem[x])return mem[x];int sum = 0;if (x > n) sum = 0;else sum = max(dfs(x + 1), dfs(x + 2) + arr[x]);mem[x] = sum;return sum;
}
int main(void)
{cin >> t;while (t--){cin >> n;for (int i = 1; i <= n; i++)scanf_s("%d", &arr[i]);memset(mem, 0, sizeof mem);int res = dfs(1);}return 0;
}

跟跳台阶一样的套路，创建一个数组，存放数据。

3.递推实现

前面也说过了，递推的过程就是递归的“归”，由搜索树的最底层开始向上推，并且递推的公式就是向下递归的公式.

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1e5 + 10;
int arr[N];
//int mem[N];
int f[N];
int n, t;
int res = 0;
#if 0
int dfs(int x)//x表示当前正在考虑哪家店
{if (mem[x])return mem[x];int sum = 0;if (x > n) sum = 0;else sum = max(dfs(x + 1), dfs(x + 2) + arr[x]);mem[x] = sum;return sum;
}
#endif 
int main(void)
{cin >> t;while (t--){cin >> n;for (int i = 1; i <= n; i++)scanf_s("%d", &arr[i]);//memset(mem, 0, sizeof mem);memset(f, 0, sizeof f);for (int i = n; i >= 0; i--){f[i] = max(f[i + 1], f[i + 2] + arr[i]);}//int res = dfs(1);}return 0;
}

四、数字三角形---来自洛谷

还是一样的套路，三种方法解决问题（我希望大家先自己去尝试用这三种方法动手打一下代码，哪里有不明白的直接看代码再自己理解一下，编程还是自己去上手才能看出来明白还是不明白）

1.用暴力搜索dfs

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1005;
int arr[N][N];
int n;
int dfs(int x, int y)
{if (x > n || y > n)return 0;else return max(dfs(x + 1, y) + arr[x][y], dfs(x + 1, y + 1) + arr[x][y]);
}
int main(void)
{cin >> n;for (int i = 1; i <= n; i++){for (int j = 1; j <= i; j++){cin >> arr[i][j];}}int res = dfs(1, 1);cout << res << endl;return 0;
}

2.用记忆化搜索

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 1005;
int arr[N][N];
int mem[N][N];
int n;
int dfs(int x, int y)
{if(mem[x][y])return mem[x][y];int sum=0;if (x > n || y > n) sum = 0;else sum = max(dfs(x + 1, y) + arr[x][y], dfs(x + 1, y + 1) + arr[x][y]);mem[x][y]=sum;return sum;
}
int main(void)
{cin >> n;for (int i = 1; i <= n; i++){for (int j = 1; j <= i; j++){cin >> arr[i][j];}}memset(mem,0,sizeof mem);int res = dfs(1, 1);cout << res << endl;return 0;
}

3.递推dp

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 1005;
int arr[N][N];
int f[N][N];
int n;
int main(void)
{cin >> n;for (int i = 1; i <= n; i++){for (int j = 1; j <= i; j++){cin >> arr[i][j];}}for (int i = n; i >= 1; i--){for (int j = 1; j <= i; j++){f[i][j] = max(f[i + 1][j] + arr[i][j], f[i + 1] [j + 1] + arr[i][j]);}}cout << f[1][1] << endl;return 0;
}

最后：希望读完这篇文章的你，对动态规划有了更深入的了解！

深入理解动态规划(dp)--(提前要对dfs有了解)

前言：对于动态规划：该算法思维是在dfs基础上演化发展来的，所以我不想讲的是看到一个题怎样直接用动态规划来解决，而是说先用dfs搜索，一步步优化，这个过程叫做动态规划。（该文章教你怎样一步步的…...

编程日记 2025/7/5 4:37:37

C++传送锚点的内存寻址：内存管理

文章目录 1.C/C内存分布回顾2.C内存管理2.1 内存申请2.2 operator new与operator delete函数2.3 定位new表达式 3.关于内存管理的常见知识点3.1 malloc/free和new/delete的区别3.2 内存泄漏希望读者们多多三连支持小编会继续更新你们的鼓励就是我前进的动力！ 继C语…...

编程日记 2025/7/4 17:08:27

webAPI -DOM 相关知识点总结（非常细）

title: WebAPI语法 date: 2025-01-28 12:00:00 tags:- 前端 categories:- 前端WEB API 了解DOM的结构并掌握其基本的操作，体验 DOM 在开发中的作用 API简介就是使用js来操作html和浏览器什么是DOM? 就是一个文档对象模型，是用来呈现预计于任意htm…...

编程日记 2025/7/5 4:19:00

Deepseek的RL算法GRPO解读

在本文中，我们将深入探讨Deepseek采用的策略优化方法GRPO，并顺带介绍一些强化学习（Reinforcement Learning, RL）的基础知识，包括PPO等关键概念。策略函数（policy） 在强化学习中， a…...

编程日记 2025/7/5 3:46:04

设计模式的艺术-策略模式

行为型模式的名称、定义、学习难度和使用频率如下表所示： 1.如何理解策略模式在策略模式中，可以定义一些独立的类来封装不同的算法，每个类封装一种具体的算法。在这里，每个封装算法的类都可以称之为一种策略（Strategy…...

编程日记 2025/7/5 4:21:12

MyBatis 写法

MyBatis 高效使用技巧常见 MyBatis 使用技巧，这些技巧有助于简化数据库操作，提高开发效率，并增强系统的性能。 1. 动态 SQL 动态 SQL 让开发者能够依据参数灵活地构建 SQL 语句，避免了手动拼接字符串带来的复杂性和错误风险。…...

编程日记 2025/7/5 3:49:35

Git图形化工具【lazygit】

简要介绍一下偶然发现的Git图形化工具——「lazygit」概述 Lazygit 是一个用 Go 语言编写的 Git 命令行界面（TUI）工具，它让 Git 操作变得更加直观和高效。 Github地址：https://github.com/jesseduffield/lazygit 主要特点主要…...

编程日记 2025/7/5 4:08:46

K8s运维管理平台 - xkube体验：功能较多

目录简介Lic安装1、需要手动安装MySQL，**建库**2、启动命令3、[ERROR] GetNodeMetric Fail:the server is currently unable to handle the request (get nodes.metrics.k8s.io qfusion-1) 使用总结优点优化补充1：layui、layuimini和beego的详细介绍1.…...

编程日记 2025/7/5 4:32:56

5.3.1 软件设计的基本任务

文章目录软件设计解决的问题概要设计基本任务详细设计基本任务软件设计解决的问题需求分析解决“做什么”的问题，软件设计解决“如何做”的问题。软件设计分为概要设计、详细设计两块。概要设计是设计软件和数据的总体框架，比详细设计的颗粒度更大。详…...

编程日记 2025/7/2 23:28:33

Go学习：字符、字符串需注意的点

Go语言与C/C语言编程有很多相似之处，但是Go语言中在声明一个字符时，数据类型与其他语言声明一个字符数据时有一点不同之处。通常，字符的数据类型为 char，例如 ：声明一个字符 (字符名称为 ch) 的语句格式为 char ch&am…...

编程日记 2025/7/2 15:20:05

LabVIEW无线齿轮监测系统

本案例介绍了基于LabVIEW的无线齿轮监测系统设计。该系统利用LabVIEW编程语言和改进的天牛须算法优化支持向量机，实现了无线齿轮故障监测。通过LabVIEW软件和相关硬件，可以实现对齿轮箱振动信号的采集、传输和故障识别，集远程采集、数据库存储…...

编程日记 2025/7/5 4:35:13

基于SpringBoot的租房管理系统（含论文）

基于SpringBoot的租房管理系统是一个集订单管理、房源信息管理、屋主申诉处理、用户反馈等多项功能于一体的系统。该系统通过SpringBoot框架开发，拥有完善的管理员后台、屋主管理模块、用户功能模块等，适用于房地产租赁平台或中介公司进行日常管理与运营…...

编程日记 2025/7/1 5:24:53

剑指 Offer II 008. 和大于等于 target 的最短子数组

comments: true edit_url: https://github.com/doocs/leetcode/edit/main/lcof2/%E5%89%91%E6%8C%87%20Offer%20II%20008.%20%E5%92%8C%E5%A4%A7%E4%BA%8E%E7%AD%89%E4%BA%8E%20target%20%E7%9A%84%E6%9C%80%E7%9F%AD%E5%AD%90%E6%95%B0%E7%BB%84/README.md 剑指 Offer II 008.…...

编程日记 2025/7/5 3:56:14

【微服务与分布式实践】探索 Eureka

服务注册中心心跳检测机制：剔除失效服务自我保护机制统计心跳失败的比例在15分钟之内是否低于85%，如果出现低于的情况，Eureka Server会将当前的实例注册信息保护起来，让这些实例不会过期。当节点在短时间内丢失过多的心跳时&am…...

编程日记 2025/7/1 23:01:29

关于opencv环境搭建问题：由于找不到opencv_worldXXX.dll,无法执行代码，重新安装程序可能会解决此问题

方法一：利用复制黏贴方法打开opencv文件夹目录找到\opencv\build\x64\vc15\bin 复制该目录下所有文件，找到C:\Windows\System32文件夹（注意一定是C盘）黏贴至该文件夹重新打开VS。方法二：直接配置环境打开opencv文…...

编程日记 2025/7/5 4:29:02

重构字符串（767）

767. 重构字符串 - 力扣（LeetCode） 解法： class Solution { public:string reorganizeString(string s){string res;//因为1 < s.length < 500 ， uint64_t 类型足够uint16_t n s.size();if (n 0) {return res;}unordere…...

编程日记 2025/7/5 4:17:13

【MQ】如何保证消息队列的高性能？

零拷贝 Kafka 使用到了 mmap 和 sendfile 的方式来实现零拷贝。分别对应 Java 的 MappedByteBuffer 和 FileChannel.transferTo 顺序写磁盘 Kafka 采用顺序写文件的方式来提高磁盘写入性能。顺序写文件，基本减少了磁盘寻道和旋转的次数完成一次磁盘 IO&#xff0…...

编程日记 2025/7/1 16:34:38

通义灵码插件保姆级教学-IDEA(安装及使用)

一、JetBrains IDEA 中安装指南官方下载指南：通义灵码安装教程-阿里云步骤 1：准备工作操作系统：Windows 7 及以上、macOS、Linux； 下载并安装兼容的 JetBrains IDEs 2020.3 及以上版本，通义灵码与以下 IDE 兼容&…...

编程日记 2025/7/4 18:13:24

babylon.js-3：了解STL网格模型

网格模型上色本篇文章主要介绍如何在 BabylonJS 中实现STL网格模型上色。文章目录网格模型上色运用场景概要延申正文加载器库的支持认识 OBJ 和 STL 文件GUI 色板选择器网格模型异步加载加载动画网格模型上色官方即将弃用 ImportMesh 而推荐使用 ImportMeshAsync 说明OBJ …...

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

面向对象设计（大三上）--往年试卷题+答案

目录 1. UML以及相关概念 1.1 动态图&静态图 1.2 交互图 1.3 序列图 1.4 类图以及关联关系 1.4.1类图 1.4.2 关系类型 (1) 用例图中的包含、扩展关系（include & extend） (2) 类图中的聚合、组合关系（aggragation & composition） 1.5 图对象以及职责划…...

编程日记 2025/7/4 6:10:23

Java基础知识总结（二十四）--Collections

它的出现给集合操作提供了更多的功能。这个类不需要创建对象，内部提供的都是静态方法。静态方法： Collections.sort(list);//list集合进行元素的自然顺序排序。 Collections.sort(list,new ComparatorByLen());//按指定的比较器方法排序。 class Co…...

编程日记 2025/7/2 18:28:49

大语言模型的API接口如何操作

选择大语言模型根据自身需求和应用场景选择合适的大语言模型，如 OpenAI 的 GPT 系列、百度的文心一言、智谱的 GLM 等。需要考虑模型的性能、功能特点、适用领域、成本等因素。获取 API 密钥和凭证注册账号：访问所选大语言模型的官方平台或相关开发…...

编程日记 2025/7/1 8:13:21

【漫话机器学习系列】067.希腊字母（greek letters）-写法、名称、读法和常见用途

希腊字母（Greek Letters） 希腊字母在数学、科学、工程学和编程中广泛使用，常用于表示变量、常量、参数、角度等。以下是希腊字母的完整列表及其常见用途。大写与小写希腊字母表大写小写名称（英文）名称（…...

编程日记 2025/7/4 13:54:28

Kotlin判空辅助工具

1）?.操作符 //执行逻辑 if (person ! null) {person.doSomething() } //表达式 person?.doSomething() 2）?:操作符 //执行逻辑 val c if (a ! null) {a } else {b } //表达式 val c a ?: b 3）!!表达式 var message: String? &qu…...

编程日记 2025/7/2 9:40:33

【Python-办公自动化】实现自动化输出json数据类型的分析报告和正逆转换

分析报告 import json from pprint import pprint, PrettyPrinterdef analyze_energy_data(file_path):"""能源数据分析与结构查看函数参数：file_path (str): JSON文件路径功能：1. 加载并解析JSON数据2. 显示数据结构概览3. 交互式结构探索"""…...

编程日记 2025/7/2 7:18:28

深入理解指针（2）

数组名的理解什么是数组名？在计算机编程中，数组名是用于标识一个数组的名称。那应当如何来理解数组名呢？事实上，在数组中数组名就是数组首元素的地址。示例1： #include<stdio.h> int main() {int arr[10] …...

编程日记 2025/7/1 22:06:23

SOME/IP--协议英文原文讲解3

前言 SOME/IP协议越来越多的用于汽车电子行业中，关于协议详细完全的中文资料却没有，所以我将结合工作经验并对照英文原版协议做一系列的文章。基本分三大块： 1. SOME/IP协议讲解 2. SOME/IP-SD协议讲解 3. python/C举例调试讲解 Note: Thi…...

编程日记 2025/6/28 6:40:13

计算机网络之计算机网络主要性能

一、速率与带宽速率： 定义：数据的传送速率，也称数据率或比特率，表示单位时间内传输的比特数。单位：比特/秒（bit/s），常用单位有千比特/秒（kb/s）、兆比特/秒…...

编程日记 2025/7/1 18:28:55

家居 EDI：Haverty‘s EDI 需求分析

Havertys 成立于 1885 年，是一家历史悠久的美国家具零售商。公司致力于为客户提供高品质的家具和家居饰品，其产品线涵盖客厅、卧室、餐厅及办公家具等多个领域。电子数据交换（EDI）是一种通过标准化电子格式在商业伙伴之间进行数据…...

编程日记 2025/7/3 10:48:55

JavaScript - Web APIs（上）

Web API 介绍严格意义上讲，我们在 JavaScript 阶段学习的知识绝大部分属于 ECMAScript 的知识体系，ECMAScript 简称 ES 它提供了一套语言标准规范，如变量、数据类型、表达式、语句、函数等语法规则都是由 ECMAScript 规定的。浏览器将 ECM…...

编程日记 2025/7/3 1:25:04

【漫话机器学习系列】068.网格搜索（GridSearch）

网格搜索（Grid Search） 网格搜索（Grid Search）是一种用于优化机器学习模型超参数的技术。它通过系统地遍历给定的参数组合，找出使模型性能达到最优的参数配置。网格搜索的核心思想定义参数网格创建一个包含超参数值…...

编程日记 2025/7/2 17:43:05

MySQL 的索引类型【图文并茂】

基本分类文本生成MindMap:https://app.pollyoyo.com/planttext <style> mindmapDiagram {node {BackgroundColor yellow}:depth(0) {BackGroundColor SkyBlue}:depth(1) {BackGroundColor lightGreen} } </style> * MySQL 索引** 数据结构角度 *** B树索引*** 哈…...

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

OSCP：发送钓鱼电子邮件执行客户端攻击

概述在渗透测试领域，钓鱼攻击是一种有效的客户端攻击手段，尤其在目标用户缺乏安全意识或系统存在未修复漏洞时，成功率较高。针对Windows平台，滥用Windows库文件（.Library-ms）是一种技术性较强但易于实施的…...

编程日记 2025/7/2 13:06:12

Oracle 普通用户连接hang住处理方法

一、现象说明 $ sqlplus / as sysdbaSQL*Plus: Release 19.0.0.0.0 - Production on Wed Dec 18 16:49:19 2024 Version 19.11.0.0.0Copyright (c) 1982, 2020, Oracle. All rights reserved.Connected to: Oracle Database 19c Enterprise Edition Release 19.0.0.0.0 - Pro…...

编程日记 2025/6/29 18:07:30

一、动态规划入门

二、跳台阶问题---来自AcWing

1.用暴力搜索dfs来解

2.记忆化搜索实现

3.递推实现

二、大盗阿福---来自AcWing

1.用dfs暴力搜索

2.记忆化搜索

3.递推实现

四、数字三角形---来自洛谷

1.用暴力搜索dfs

2.用记忆化搜索

3.递推dp

相关文章：