二分

题目出现至少或者最大最小，要么是二分要么是dp，找存在单调性的参数

双指针

核心思想：优化暴力，把时间复杂度n^2优化到n，维护一些具有单调性、可快速删减的区间信息
1、要保证两个指针的单调性，即不能回头走（如果向前走就一直向前走）。

2、如果无序的话，可能需要先排个序。

3、用到的基本是 快慢指针 和 对撞指针

回溯算法套路

排列，组合，分割，子集，棋盘

void dfs()//参数用来表示状态  
{  
    if(到达终点状态)  
    {  
        ...//根据题意添加  
        return;  
    }  
    if(越界或者是不合法状态)  
        ...//根据题意添加  
        return;  
    if(特殊状态)//剪枝
        ...//根据题意添加  
        return ;
    for(扩展方式)  
    {  
        if(扩展方式所达到状态合法)  
        {  
            修改操作;//根据题意来添加  
            标记；  
            dfs（）；  
            (还原标记)；  
            //是否还原标记根据题意  
            //如果加上（还原标记）就是 回溯法  
        }  

    }  
}  

BFS

#define pair<int, int> PII
void bfs()
{
    queue<PII> q;    //一般用stl库中的queue来实现队列比较方便
    q.push(起点S);    //将初始状态入队
    标记初始状态已入队。
    while(!q.empty())//队列不为空就执行入队出队操作
    {
        top = q.front();//取出队头
        q.pop();//队首出队
        for (枚举所有可扩展的状态)
        {
            if (check())//状态合法
            {
                q.push(temp);//状态入队
                标记成已入队。
            }

        }
    }

DP小记

一、DP数组的定义和下标

线性DP：两个集合的话，f[i][j]是以i-1为结尾的sums1和以j-1为结尾的sums2的……

二、递推公式

三、初始化

四、遍历顺序

1、背包问题
    01背包先遍历背包，在遍历物品
    完全背包排列组合的遍历顺序是不同的
        （1）排列：背包在外，物品在内
        （2）组合：物品在外，背包在内

五、出现问题打印DP数组