C++ 动态规划算法基础前言动态规划(Dynamic Programming,简称DP)是算法设计中的一种重要方法,广泛应用于解决最优化问题。本文将介绍动态规划的基本概念、核心思想,以及两种常用的分析方法:常规分析方法和闫氏DP分析法。
本文导航:
📚 动态规划基础:定义、核心思想、基本要素
🔄 解题步骤:五步法解决DP问题
📖 常规分析方法:传统DP分析方法
🎯 闫氏DP分析法:集合角度的系统化方法
⚖️ 两种方法对比:选择适合的分析方法
📦 常见DP类型:线性、区间、背包、树形、状态压缩
🚀 优化技巧:空间优化、状态优化、转移优化
💡 学习建议:如何学好动态规划
一、什么是动态规划1. 动态规划的定义动态规划是一种通过把原问题分解为相对简单的子问题的方式来解决复杂问题的方法。它通常用于解决具有重叠子问题和最优子结构性质的问题。
动态规划的核心思想是:
记忆化:避免重复计算已经求解过的子问题
自底向上:从最小的子问题开始,逐步构建更大问题的解
状态转移:通过状态转移方程描述问题之间的关系
2. 动态规划与贪心、分治的区别动态规划、贪心算法和分治 ...
前言STL(Standard Template Library) 是C++标准库的重要组成部分,提供了丰富的数据结构和算法,大大提高了C++程序开发的效率。
本文详细介绍STL中常用容器、迭代器、算法等的基本用法,帮助读者快速掌握STL的使用。
本文包含以下内容:
STL简介和六大组件
13种常用容器的详细用法(string, vector, list, stack, queue, priority_queue, deque, set, map, multiset, multimap, unordered_set, unordered_map)
迭代器的使用
常用算法的介绍
函数对象和Lambda表达式
实用技巧和最佳实践
STL简介什么是STLSTL(Standard Template Library) 是C++标准模板库的简称,是C++标准库的核心组成部分。
STL的特点:
模板化:使用模板技术,支持泛型编程
高效性:经过优化的数据结构和算法实现
可复用性:提供了大量可复用的组件
标准化:是C++标准的一部分,跨平台兼容
STL的优势:
提高开发效率:无需重复实 ...
前言本文将带你深入学习 C++ 中的搜索算法,包括DFS(深度优先搜索)、BFS(广度优先搜索)和洪泛算法,让你掌握这些重要的算法思想,能够解决各种搜索问题!
在阅读过程中有任何问题都可以发布到评论区,有价值的问题将会放到文章末尾Q&A之中!
本文导航:
🔍 DFS(深度优先搜索):深入理解递归搜索
📊 BFS(广度优先搜索):层层递进的搜索策略
🌊 洪泛算法:连通性问题的经典解法
💡 实战练习:经典题目训练
⚠️ 常见错误:易错点分析
🚀 编程技巧:优化建议
DFS(深度优先搜索)什么是DFSDFS(Depth-First Search,深度优先搜索)是一种重要的搜索算法,它采用”一条路走到黑”的策略:
🌲 树/图的遍历:从起点开始,沿着一条路径尽可能深地搜索,直到无法继续,然后回溯到上一个节点,继续搜索其他路径
🔄 递归思想:DFS通常用递归实现,代码简洁优雅
📍 回溯机制:当一条路径走不通时,会返回到上一个状态继续尝试
DFS的核心思想:
先深入后回溯,像走迷宫一样,遇到死胡同就回头
用一个递归函数来模拟这个过程
需要标 ...
前言本文记录各种高精度运算的相关实现思路以及 C++ 代码描述。
在阅读过程中有任何问题都可以发布到评论区,有价值的问题将会放到文章末尾Q&A之中!
高精度运算高精度算法(High Accuracy Algorithm)是处理 大数字【数字长度大于10^6】 的数学计算方法。在一般的科学计算中,会经常算到小数点后几百位或者更多,当然也可能是几千亿几百亿的大数字。一般这类数字统称为高精度数,高精度算法是用计算机对于超大数据的一种模拟加,减,乘,除,乘方等运算。对于非常庞大无法在计算机中正常存储的数字,将这个数字拆开,拆成一位一位或者是四位四位的存储到一个数组中, 用一个数组去表示一个数字,这样这个数字就被称为是高精度数。
高精度运算的基本思想就是通过将数字逐位拆分到数组之中后,模拟人工计算时列竖式的过程来完成对高精度数字的运算。
高精度加法实现思路详解数据存储在加法计算的过程中,将加数的每一位都放到一个数组之中,注意在存储的过程中要逆序存储
12345678910// 首先将两个加数都用字符串来表示,因为精度过大,所以使用常规的整型无法存储// 字符串每个字符占用 ...
前言本文记录 C++ 相关的结构体的相关知识。
在阅读过程中有任何问题都可以发布到评论区,有价值的问题将会放到文章末尾Q&A之中!
什么叫结构体在生活中,我们的书包内可以同时放入语文书、数学书、文具盒等等不同类型的物品。
这些物品的类型不同,但是都是属于你的学习用品。
在程序中,结构体的功能和书包相同,就是将相关但是不同的数据类型“打包”在一起。
为什么要“打包”数据比如说在一个班级中,每个学生都有自己的姓名、学号、成绩等等不同的信息。
如果这些信息是相对独立的,那么就没办法通过学生的姓名查询到成绩,学号等等相关信息。
在代码中,我们也可以模拟一下这种情形。
12345678910#include <iostream>using namespace std;int main(){ int id, sorce; string name; return 0;}
使用这种方法来定义的话,必须通过判断的形式来获取到相关联的信息,特别麻烦。
123456789101112131415161718#includ ...
前言本文记录 C++ 相关的函数的相关知识。
在阅读过程中有任何问题都可以发布到评论区,有价值的问题将会放到文章末尾Q&A之中!
函数示例函数实现Hello World123456789101112#include <iostream>using namespace std;void fun(){ cout << "Hello World!" << "\n"; }int main(){ fun(); return 0;}
函数实现阶乘1234567891011121314151617181920#include <iostream>using namespace std;int fun1(int n){ int res = 1; for(int i = 1; i <= n; i ++ ){ res *= i; } return res;} ...
前言本文记录 C++ 相关的字符串的相关知识。
在阅读过程中有任何问题都可以发布到评论区,有价值的问题将会放到文章末尾Q&A之中!
什么是字符串由多个字符组成的长序列叫做字符串。
字符串是计算机和人类进行沟通的手段之一。
人类以字符串形式向计算机输入代码指令,计算机将其转化为 01 代码进行识别,最后将结构再以字符串形式展示给人类。
ASCII码表在计算机内部,每个字符都对应有一个整数进行表示,计算机再将这个整数转化为二进制进行识别。
这个字符与整数对应的表为 ASCII 码表。
具体对应关系如下图所示。
在使用的过程中,常用的字符有:'0' 对应整数 48,'A' 对应整数 65, 'a' 对应整数 97。
在使用 ASCII 码表时,无需特殊记忆所有的内容,在做题过程中如果需要用到该表可以直接打表输出即可。
1234567891011#include <iostream>using namespace std;int main(){ // 常用的 ASCII 码值范围为 0 ...
前言本文记录 C++ 相关的数组的相关知识。
在阅读过程中有任何问题都可以发布到评论区,有价值的问题将会放到文章末尾Q&A之中!
什么是数组想要同时定义多个同类型的变量,可以使用数组定义。
12345// 定义三个 int 类型的变量,分别为 a, b, cint a, b, c;// 定义三个 int 类型的变量,分别为 a[0], a[1], a[2]int a[3];
一维数组定义数组的定义和变量的定义方式是类似的。
只需要在变量名后使用 [ ] 声明变量的长度。
具体格式:数组类型 变量名[长度]
12345// 整型数组,长度为 110int a[110];// 字符数组,长度为 30char s[30];
初始化数组的初始化有如下几条规则:
未初始化的数组其每个元素值是不确定的。
初始化的数组可以不填写数组的长度,让其自动识别长度。
当定义长度大于初始化的元素个数时,其余未初始化的元素自动为 0
12345678910111213141516171819202122#include <iostream>using namesp ...
前言本文记录 C++ 相关的循环结构的相关知识。
在阅读过程中有任何问题都可以发布到评论区,有价值的问题将会放到文章末尾Q&A之中!
循环结构在 C++ 中,当程序需要多次执行同一块代码时,一般会用到循环结构
程序结构图大部分的循环语句均满足下面这个程序结构图。
循环语句C++ 中有三种方式实现循环结构。分别为 while 循环、do-while 循环、for 循环
while 循环while 循环的基本结构与 if 判断语句类似,只需在括号中写明条件即可。
区别是 while 循环,当条件满足时,将一直执行循环内部语句,直到条件不满足。
123while(判断条件){ ……; // 如果判断条件为真将执行的语句}
实例123456789101112131415161718#include <iostream>using namespace std; int main (){ // 局部变量声明 int a = 10; // while 循环执行 while( a < 20 ...
前言本文记录 C++ 相关的判断结构的相关知识。
在阅读过程中有任何问题都可以发布到评论区,有价值的问题将会放到文章末尾Q&A之中!
判断结构在 C++ 中,程序运行的过程会通常会指定一个或者多个要评估的条件,以及指定满足该条件的情况下【条件为真】要执行的语句,与不满足该条件时【条件为假】要执行的语句。
程序结构图大部分的判断语句均满足下面这个程序结构图。
判断语句C++ 中提供了 if …… else 语句来实现判断功能。
if 语句单个 if 语句常用来实现只有一种判断条件的情况,具体的格式如下。
123if(判断条件){ ……; // 如果判断条件为真将执行的语句}
实例1234567891011121314151617181920#include <iostream>using namespace std; int main (){ // 局部变量声明 int a = 10; // 使用 if 语句检查布尔条件 if( a < 20 ) { ...










