背包问题：
一.
先看是“至多”，“恰好”，“至少”(不对就换):
1.初始化都各不相同 
2.以单一费用举例,“至多”，“恰好”的背包限制了大小,不可超载:j >= v;“至少”的背包不限制大小,可超载: j >= 0。
(https://www.acwing.com/solution/content/7438/) 
3.“恰好”的情况算完时，要对结果扫一遍。

二.
再看是什么背包:
01背包：原理 (https://www.acwing.com/activity/content/code/content/6894618/)
完全背包：原理 (https://www.acwing.com/activity/content/code/content/6898318/)
分组背包：1.原理 2.以体积和组来划分的依赖背包
(https://www.acwing.com/activity/content/code/content/6903634/)
多重背包:利用二进制转化为01背包即可。
混合背包:对不同类型的物体进行不同的处理
(https://www.acwing.com/activity/content/code/content/7042030/)

三.记录具体方案：第一维不可省略(https://www.acwing.com/problem/content/1015/)

四.求方案数：由于本身是拓扑序，可边求最大（小）值，边求方案数
(https://www.acwing.com/activity/content/code/content/7050632/)

背包问题集合的划分：
前 i 个物体（组），j 体积的最大价值：分配给第 i 个物品（组）合法的体积，
把剩下的体积给前 i-1 个物品（组），在这些值中找到最大值

最长子序列：
1.掌握求最长上升子序列的两种算法
2.掌握求最长公共子序列的算法：以a,b序列最后一个字符是否在最长公共子序列中来进行集合划分

状态机模型：把一个点拆成多种状态

区间dp(https://www.acwing.com/activity/content/code/content/7107453/)

树形dp:1.求树的直径2.求一个点离另一个点最远的距离

图论：
一.
1)乘法最小值
1.>=1：dijkstra 理由：算法的前提是st数组里的都是已经确定最小值的，若存在<1的话会破坏这个前提。
2.>0：spfa

2)乘法最大值
1.>0 <=1:dijkstra
2.>0:spfa

边权必须要大于0，因为取对数后真数的取值范围要大于0.

二.
dijkstra:加法最小值，边权非负。
spfa:加法最大值和最小值都能求,边权可正可负。

三.
为什么dijkstra只能在正权图上使用:
回顾 dijkstra算法的思想，他是基于贪心,对于寻找单源最短路，每次找到全图 dist最小的那个点来
更新其他点保证了在st数组中的点不会再被更新，如果是正权图的话dist只会越来越大，所以能保证
这个性质。但是对于负权图， dist不一定是单调增大的，因此这个点不能被确认已经是最终dist,即
最小的情况。
总结:只要保证dist是越来越大的，就能保证确定了最小距离的点再也不会被更新掉,那么对于最长路，
我们只要保证 dist是越来小的，才能保证确定了最大距离的点再也不会被更新掉.

四.
bfs,dijkstra,spfa的区别:
1.bfs中一个点在第一次遍历的时候就已经是最短值,st数组用于确定是否遍历过了
2.dijkstra在出队时判重,st数组用于确定是否已确定了最短值
3.spfa在拿到一个点后就去更新其邻接点,st数组用于确定是否在队列中，防止重复入队

五.单源最短路:
1.综合应用：与dfs,二分,拓扑排序等结合
2.常用扩展应用：虚拟源点；先用dp的方式思考，再转化为图；拆点；最短路计数。
（如果要求最短路条数，那么正在求的量所依赖的量已经被求出，即该图是一个拓扑图，不存在值为0的环，
而bfs和dijkstra求最短路时是一个拓扑序，满足要求，可以边求最短路的值，边把最短路条数求出来，
而spfa不满足，应先将最短路的值求出来，再根据d[j]==d[p]+w[i]是否成立，判断该边是否在最短路上，
即拓扑图上，求出最短路条数）

六.floyd
1.划分原理
2.记录路径
3.传递闭包