什么是剪枝？

常用的搜索有DFS和BFS。
BFS的剪枝通常就是判重，因为一般BFS寻找的是步数最少，重复的话必定不会在之前的情况前产生最优解。

深搜，它的进程近似一颗树(通常叫DFS树)。
而剪枝就是一种生动的比喻：把不会产生答案的，或不必要的枝条“剪掉”。

剪枝的关键就在于剪枝的判断：什么枝该剪，什么枝不该剪，在什么地方减。

剪枝的原则？

正确性，准确性，高效性。
常用的剪枝有：可行性剪枝、最优性剪枝、记忆化搜索、搜索顺序剪枝。

1.可行性剪枝

如果当前条件不合法就不再继续搜索，直接return。这是非常好理解的剪枝，搜索初学者都能轻松地掌握，而且也很好想。一般的搜索都会加上。

一般格式：

dfs(int x)  
{  
    if(x>n)return;  
    if(!check1(x))return;  
    ....  
    return;  
}  

2.最优性剪枝

如果当前条件所创造出的答案必定比之前的答案大，那么剩下的搜索就毫无必要，甚至可以剪掉。
我们利用某个函数估计出此时条件下答案的‘下界’，将它与已经推出的答案相比，如果不比当前答案小，就可以剪掉。

一般格式：

long long ans=987474477434487ll;  
... Dfs(int x,...)  
{  
    if(x... && ...){ans=....;return ...;}  
    if(check2(x)>=ans)return ...;    //最优性剪枝   
    for(int i=1;...;++i)  
    {  
        vis[...]=1;   
        dfs(...);  
        vis[...]=0;  
    }  
}  
//一般实现：在搜索取和最大值时，如果后面的全部取最大仍然不比当前答案大就可以返回。  
//在搜和最小时同理，可以预处理后缀最大/最小和进行快速查询。  

3.记忆化搜索

记忆化搜索其实很像动态规划（DP）。

它的关键是：如果对于相同情况下必定答案相同，就可以把这个情况的答案值存储下来，以后再次搜索到这种情况时就可以直接调用。

还有就是不能搜出环来，不能互相依赖。

一般格式：

long long ans=987474477434487ll;  
... Dfs(int x,...)  
{  
    if(x... && ...){ans=....;return ...;}  
    if(vis[x]!=0)return f[x];vis[x]=1;  
    for(int i=1;...;++i)  
    {  
        vis[...]=1;   
        dfs(...);  
        vis[...]=0;  
        f[x]=...;  
    }  
}  

4.搜索顺序剪枝...

掌握搜索剪枝技巧