8.记忆化搜索记忆化搜索就是对于某个子问题的解可能会被多次用到，那么就把子问题的解保存起来，以后用到的时候直接用，不用再计算一遍，以滑雪这道题为例，多条路径可能经过同一个点，那么就把这个点的值保存起来，只计算一次。 AcWing 901. 滑雪实现思...

2.Huffman树-哈夫曼树实现思路：构建一颗哈夫曼树，求最短带权路径长度（树中所有的叶结点的权值乘上其到根结点的路径长度） 每次选择重量最小的两堆进行合并 使用小根堆存储每一堆果子，每次两次弹出堆顶元素，合并后就放入小根堆中 12345678...

1.区间问题AcWing 905.区间选点实现思路： 将每个区间按照右端点从小到大排序 从前往后依次枚举每个区间 若当前区间中已经包含点，则跳过 否则(即当前区间的左端点大于该点)，选择当前区间的右端点 证明：比较最终结果ans和选出的点个数...

3.排序不等式AcWing 913.排队打水实现思路： 假设各个同学的打水时间为：3 6 1 4 2 5 7 并且就按照这个顺序来打水。 当第一个同学打的时候，后面所有同学都要等他，所以等待的总时长要加上一个3 * 6，第二个同学打的时候，后面所有同...

1.DFS与BFSDFS：深度优先搜索（Depth-First-Search） BFS：宽度优先搜索（Breadth-First-Search） DFS和BFS的对比 DFS使用栈（stack）来实现，BFS使用队列（queue）来实现 DFS所需...

4.绝对值不等式AcWing 104.货仓选址实现思路： 假设n个商店在数轴上的坐标依次为：x1，x2，x3，…，xn 设仓库的位置为x，则总的距离为 1f(x) = |x1 - x| + |x2 - x| + ... + |xn - x| 我们要...

（三）组合计数$$从a个元素中选择b个，有多少种取法C_{a}^{b} = \frac{a\times(a-1)\times\dots\times(a-b+1)}{1\times2\times3\times\dots\times b}\&#...

5.推公式AcWing 125. 耍杂技的牛实现思路：wi表示牛的体重，si表示牛的强壮度 先给结论：按照w + s从小到大的顺序，从上往下排，最大的危险系数一定是最小的。 简单理解：把重量轻的牛放下面是很亏的，同样把不强壮的牛放下面也是亏的，所以就...

1.背包问题什么是背包问题？ 给定N个物品和一个容量为V的背包，每个物品有体积和价值两种属性，在一些限制条件下，将一些物品装入背包，使得在不超过背包体积的情况下，能够得到的最大价值。根据不同的限制条件，分为不同类型的背包问题。 0-1背包问题给定N个...