递推求组合数

1、组合数中有 $C_n^m = C_{n-1}^{m-1} + C_{n-1}^m$ 。其中 $C_n^m$ 意为从 $n$ 个元素中选出 $m$ 个元素有多少种不同组合，其总的可能可划分为组合中选了第一个和组合中没选第一个两种。如果组合中选了第一个，那么剩下的方案数还有 $C_{n-1}^{m-1}$ 种(从剩余元素中选 $m-1$ 个)；如果组合中没选第一个，那么剩下的组合中还有 $C_{n-1}^m$ 种；这两种结果互斥，因此相加便可得到总的方案
2、这种方法运用了递推与DP的思想，上面的等式为状态转移方程。其中，$C_n^m$ 为新状态，通过方程将其转移为两个老状态的和。此外，需要确定起始点和边界：起始点为 $C_i^0 = 1$ (从任意多的元素中选 $0$ 个，有 $1$ 种方案——不选)；边界为 $C_i^j$ (其中 $0 \leq j \leq i$，$i \leq n$)

生成树 与 MST

1、在无向连通图中，找出一个节点最多的子连通图(有 $n$ 个点，$n-1$ 条边)，这样的子连通图一定是树，称为生成树。最小生成树指各边权值之和最小的生成树，称为 MST(Minimum Spanning Tree)
2、如下图，便是一幅无向连通图，该图的最小生成树为图中红色所示的子连通图(有 $5$ 个点，$4$ 条边)，其权值和为 $10$
3、对于最小生成树的生成，可以通过基于点的 Prim 最小生成树与基于边的 Kruskal 最小生成树完成

Dijkstra 朴素算法

1、最短路 1：给定 $n$ 个点 $m$ 条边的有向图($n \leq 10^3, m \leq 10^5$)，输出点 $1$ 到 $n$ 的最短距离。对于 $m$ 条边，每次输入 $u、v、w$ ，表示存在一条从 $u$ 到 $v$ 的权值为 $w$ 的有向边。如果不存在路径，输出 $-1$
2、先前在图与回溯中介绍过无权最短路，现在有了权值，需要做一个结构体保存。Dijkstra还使用一个数组 $d[]$ ，$d[i]$ 表示从起点 $st$ 到 $i$ 的最短距离
3、Dijkstra 思路如下图：起始时，建图，标记所有 $d[i]$ 为 $\infty$，以 $1$ 为起点，向外走一层，将经过的边松弛(用边的权值更新所到点的 $d[i]$ ，$d[i]$ 取较小值)；接下来，比较得到最小的 $d[i]$ ，以该点为当前起点(图中为点 $2$)，先前的点已经可以忽略，继续向外走一层，将经过的边松弛(注意，$d[3]$ 取较小值更新为 $3$)；以此类推，以 $4$ 为当前起点发现点 $4$ 没有出点，返回；以 $3$ 为当前起点，走到终点，更新 $d[5]$ 为 $6$，所以最短路为 $6$
4、该算法结合了贪心和DP的思想，每个点只拓展一次，且拓展时已为最短距离

并查集

1、并查集是一种支持合并和查询操作的集合形式的数据结构，它支持两个集合的合并，并可以查询点与点之间的连通关系
2、并查集只需要一个数组 $pre[]$ 存储点的前导点(父节点)，在初始化时 $pre[i] = i$ ，表示点与自己连通，是单独的连通块，该功能由 $init()$ 函数完成。并查集中还需要一个函数 $root(u)$ ，该操作将找到点 $u$ 所属的连通块(的根节点)。该函数将递归查找 $u$ 的父节点，直至找到根节点
3、对于两个点 $u$ 和 $v$ 的合并操作，只需要将 $u$ 和 $v$ 所属的连通块的其中一个根指向另一个根，即 $pre[root(u)] = root(v)$ ；对于两个点 $u$ 和 $v$ 的查询操作，只需要判断 $u$ 和 $v$ 所属的连通块的根是否相同
4、但前述 $root(u)$ 函数的朴素算法每次都需要查找一整条父节点链，效率太低，可以通过路径压缩优化程序： pre[u] = (pre[u] == u ? u : root(pre[u]))，这样同一连通块在第一次查找后，每个节点都将直接指向当前根节点，提高以后查找的效率，时间复杂度接近 $O(1)$

树状数组

1、树状数组常用于维护区间和，有以下操作：单点修改 $O(\log n)$，区间修改 $O(\log n)$，区间查询 $O(\log n)$
2、树状数组的结构如下图，注意树状数组中一定不能用下标 $0$ 。$T[i]$ 所存的值为管辖区间的和，$T[i]$ 所覆盖的管辖区间为 $[i - lowbit(i) + 1, i]$ ，管辖区间长度为 $lowbit(i)$
3、$lowbit(i)$ 表示 $i$ 的二进制只保留最后一位 $1$ 的结果(例如二进制 $1101100$ 只保留后三位变为 $100$)，公式为 $lowbit(x) = x \land -x$

单调栈

1、在栈的基础上，如果保持栈内元素是有序的，则称为单调栈，分为单调递增栈和单调递减栈
2、通常单调栈主要用于求位置最近的更大值或更小值，我们将在具体样例中分析

适用前提

1、简言之：可以找到一个局部最优解；可以从局部最优解推广到全局最优解
2、严谨地说，两个条件分别是最优子结构和贪心选择性质
3、一般来说，贪心法往往是将某个东西排序，或者用堆(优先队列)等数据结构，每一步都取局部最优解，进而得到全局最优解

邻接表

1、在计算机中，图的存储方式有多种，最常用的是邻接表和邻接矩阵。邻接矩阵由于适用范围很小，故一般不考虑这种写法
2、出度：如下图便是一幅有向图，其中一个节点指向的其他节点称为这个节点的出度，指向出度节点的路径称为这个节点的出边。如下图中 $2$、$5$ 为 $1$ 的出度
3、邻接表：就是将一个点的所有出点(邻接点)保存在一个数组中；拓展的过程，也就是遍历这个数组的过程。这个数组我们称为邻接表