[2024年度博客之星] 基础算法总结

本文主要是对一些普及组的算法的简单总结（主要是框架），并不适合新手阅读，若有错误，敬请斧正。

---

两种大的解题思路

递归

将原问题分成相似的更小的子问题，一直分下去，得到子问题的答案后，返回来求出原问题。

递推

由已知状态开始，推出未知状态，从而得到问题的答案。

基于递归的算法

分治

分而治之，先将原问题分为子问题，再将子问题的答案合并得到原问题的答案。

搜索DFS

从起点开始，递归出可能的情况，不断递归下去，得到答案。

---

基于递推的算法

搜索BFS

用队列进行维护。先将起点加入队列。每次取出队首，扩展出可能的情况，加入队列中，直到得到答案为止。

动态规划DP

就是递推问题，只不过类型复杂，固单独总结出了一个算法。
动态规划需要定义状态，初始化，推出转移方程，从而求出答案。

线性DP

在线性空间上的递推，不一定都是一维的。

背包

01背包
在 $n$ 个物品的选与不选之间的递推。
完全背包
$n$ 个物品可以选无数次的递推。
多维费用背包
只是把层数增加了，仍然和背包类似。
多重背包
进行二进制拆分，优化时间复杂度。

部分和DP

在一个序列/矩阵/……中的和/积/最值问题。

区间DP

从小区间转移到大区间。

树形DP

在树上进行各种DP。

---

搜索优化

剪枝

可行性剪枝
提前剪掉不满足条件的状态。
最优性剪枝
提前剪掉不可能是最优解的状态。

记忆化

将搜索中的重复内容记录下来，避免重复计算。

迭代加深

限定搜索层数，从 $1$ 开始，增加搜索层数，直到搜到结果为止，避免DFS在一棵树上搜半天没得到答案，而另一棵树在很浅的位置就能得到答案。

折半搜索

先搜前一半，然后搜后一半，在两次搜索的连接处统计答案，复杂度的指数约能减少一半。

双向宽搜

从起点和终点开始，同时扩展，直到相遇为止。

---

二进制思想

二进制拆分

任意一个数都能拆分成 $2$ 的整数幂次方的和。

倍增

倍增，即成倍增长，通常当空间和时间复杂度超出题目限制时，可以只处理 $2$ 的整数幂次方，再将它们合并起来得到答案。
ST表
ST表，是求解 RMQ问题中的一个方法，思路基于倍增。ST表用 $O(nlogn)$ 的时间预处理 $2$ 的整数幂次方，$O(1)$ 的时间求得答案。

状态压缩

将一个 bool 数组，压缩成一个整数。

二分

将一个问题的求解分为左右两段，找到满足条件的一段继续分下去，直到得到答案。
若题目具有单调性，则可以将答案进行二分，缩小答案的范围，从而得到答案。

---

贪心思想

贪心，从局部的最优能推得全局的最优。做贪心题时，选择最优的方法需要保证正确性，因此需要证明，主要证明方法有数学归纳法，反证法，邻项交换等。

---

这是我第一次参加博客之星，我本来想将数据结构加进去的，可是我时间不够，而且我决定将提高组的数据结构也加进去，请大家谅解。

原文地址：https://blog.csdn.net/m0_64542522/article/details/145270419

免责声明：本站文章内容转载自网络资源，如侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！