2.线性DP状态转移方程呈现出一种线性的递推形式的DP，我们将其称为线性DP。 （一）数字三角形AcWing 898. 数字三角形实现思路： 对这个三角形中的数字进行编号，状态表示依然可以用二维表示，即f(i,j)，i表示横坐标（横线），j表示纵坐...

4.计数类DPAcWing 900. 整数划分实现思路：本题求的是方案个数，而不要求方案顺序，即4=1+1+2 和4=1+2+1是一样的 （1）方案一：转化为完全背包做法。将正整数n看做是背包容量，而1~n之间的数看做是物品，且各...

5.数位统计DPAcWing 338. 计数问题实现思路： 定义函数：count(n,x)，其表示在1到n中，x出现的次数（x是0-9） 那么，可以用类似前缀和的思想，来求解a到b中，x出现的次数：count(b,x) - count(a-1,x)...

6.状态压缩DP将一个十进制的整数转化为二进制数，每一位表示一种状态 AcWing 291. 蒙德里安的梦想实现思路：先放横着的，再放竖着的。 总方案数，等于只放横着的小方块的合法方案数。（放完横着的方块之后，竖着的只能被动填充进去，不需要额外进行竖...

7.树形DPAcWing 285. 没有上司的舞会实现思路：所求即为从一棵中选出一个结点集合其各结点的值之和最大，且这个结点集合中都没有这些结点的父节点存在（没有父亲，只有同辈或者隔辈） 状态表示：利用递归 f(u, 0)：从所有以u为根结点的子树...

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所需...