Meet in the middle（MITM）

搜索

作业部落

评论地址

PPT中会讲的很详细
当搜索的各项互不影响（如共$n$个物品前$n/2$个物品选不选和后$n/2$个物品选不选互不干扰）且状态数小得可怜的时候可以考虑双向搜索（MITM）
实现非常灵活，具体看题
精髓是：用空间换时间

• [SPOJ4580]ABCDEF☃☃
• [NOI2001]方程的解数☃☃
• [TopCoder14580] EllysRPS☃☃☃
• [BZOJ4800]Ice Hockey World Championship☃☃☃
• [Codeforces888E]Maximum Subsequence☃☃☃
• [ZOJ3777] Problem Arrangement☃☃
• 八数码难题☃☃☃