主要知识点：
经典贪心：
贪心算法（又称贪婪算法）是指，在对问题求解时总是做出在当前看来是最好的选择。然后通过局部的贪心来达到问题的全局最优解
运用贪心策略解题，一般来说需要一步步的进行多次的贪心选择。
在经过一次贪心选择后，原问题将变成一个相似的，但规模更小的问题
而后的每一步都是当前看似最佳的选择，且每个选择都仅做一次
贪心和动态规划的区别：
动态规划可以认为是含有重叠子问题的暴力算法，问题可以分解成多个子问题，子问题之间存在重叠，需要用动态规划表格记录在中间结果，本质还是要穷举所有解空间
而贪心的精髓在于不用穷举所有解空间，就能找到答案。每一步都需要进行选择，选择需要满足贪心选择性质，问题具有最有子结构性质，子问题之间相互独立
如何判断这个题目适合使用贪心算法呢？
1、数学证明（难度较高，不推荐）
2、凭感觉（举不出反例就行）
3、观察题目数据范围
如果在20以内，那么就是指数级别的算法
如果数据范围较小，允许O（nn）或O（nn*n）的时间复杂度，那就可能是要用dp
如果数据范围很大，那么就可能是贪心的解法
4、多积累经验，学习各种类型的贪心题
朴素贪心：
贪心算法是指在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，算法得到的是在某种意义上的局部最优解
贪心算法不是对所有问题都能得到整体最优解，关键是贪心策略的选择
除了经典的、有模板的贪心题外，还有很多需要灵活思考和创造性解决的贪心问题，这些问题可能需要考虑多种因素，或者需要利用特殊的性质来优化贪心策略
同时贪心算法也可以和其他算法结合使用比如动态规划和二分查找等，进一步提高问题的解决效率。
总之，贪心算法是算法竞赛中不可或缺的一部分，需要我们不断学习和探索
二分查找：
二分查找是一种查找方法
二分查找，也称折半查找，是一种在有序数组中查找特定元素的搜索算法
该算法的时间复杂度为O（log n），比起线性查找的时间复杂度O（n）要更快
二分查找的实现步骤：
1、初始化左右指针和中间指针
2、循环比较中间元素和目标元素的大小关系，如果相等则返回中间指针，如果目标元素小于中间元素，则在左半部分继续查找，否则在右半部分继续查找
3、更新左右指针和中间指针
4、重复步骤2和3直到找到目标元素或者确定目标元素不存在为止
适合使用二分查找的题目：
当问题的答案具有单调性时，我们就可以用二分查找
单调性可以理解为：
随着x的增加，对应y值逐渐增大——单调递增
或随着x值的减小，对应y值逐渐减小——单调递减
二分查找的题目特征：
一般情况下题目问什么就二分什么，分析问题，接着寻找可能答案的最小值L和最大值R
搜索：
深度优先搜索（DFS）：
DFS的主要思路：
从图中一个未访问的顶点V开始，沿着一条路一直走到底，然后从这条路尽头的节点退回到上一个节点，再从另一条路开始走到底不断递归重复此过程，直到所有的顶点都遍历完成
DFS的特点是“不撞南墙不回头”，先走完一条路，再换一条路继续走
DFS的基本框架：
（DfS一般使用递归去实现）
void DFS(typename name){
if(符合条件){ （递归的中止条件）
cout<<答案;
return ;
}
for(选择该阶段可以访问的所有节点){
确定新点
if(判断新点是否越界){
continue;
}
标记已访问该点
DFS(n+1);
取消标记（回溯）
}
}
DFS的分类：
1、迷宫类DFS
2、棋盘类DFS
广度优先搜索（BFS）：
BFS的主要思路：
从图的一个未遍历的节点出发，先遍历这个节点的相邻节点，再依次遍历这个相邻节点的相邻节点
每个节点的值即为它们的遍历顺序，所以广度优先搜索也叫层序遍历
BFS的代码框架：
void BFS（起始状态）{
queuename;
q.push(起始状态);
while(q.size() 或 !q.empty()){
node hd=q.front();
q.pop(起始状态);
for(选择该阶段可以访问的所有节点){
确定新点
if(判断新点是否越界){
continue;
}
标记新点
q.push(当前状态);
}
}
}
搜索的剪枝：
在我们的搜索中，我们可以提前制定一些策略，来优化我们的搜索
那么，这个优化策略，在算法中我们称之为——剪枝
常见的剪枝方法：
1、优化搜索顺序：
在一些搜索问题中，搜索树的各个层次、各个分支之间的顺序是不固定的。不同的搜索顺序会产生不同的搜索树形态，其规模大小也相差甚远
2、可行性剪枝：
在搜索过程中，可以及时检查当前状态，如果我们发现递归分支已经无法到达边界，就执行回溯
3、最优性剪枝：
在最优化问题的搜索过程中，如果当前花费的成本超过了当前搜索到的最优解，则停止搜索当前分支，执行回溯
4、消除等效冗余：
在搜索过程中，如果我们可以确定从当前子树节点沿着搜索树到达几个不同的分支是等价的，那么只有对其中一个分支进行搜索
5、记忆化搜索：
可以记录每个状态的搜索结果，在重复遍历一个状态时直接检索并回溯（详见下一章）
记忆化搜索：
在我们遍历一个图时，有可能会重复计算某一个节点
那么我们可不可以把这些重复计算的东西记录起来？这样不就可以大大节约我们的时间了吗？
我们用一个最原始的数组把需要计算的值记录下来，这样的话，我们就相当于告诉计算机：“你别傻傻每一次都去算啦，找个东西记一下吧！”
记忆化搜索的概念：
对递归树做了剪枝（详见上一章），搜索过的子树不在重复搜索，直接返回存储值
利用数组来记录已经计算出来的重叠子问题
谢谢观看~~