大一懵逼系列

小优化，re不需要是map，可以是unordered_map或者int数组之类。map底层实现是红黑树，查找时间复杂度并非常数。
不过，既然是dp题，为什么要用暴搜折磨自己呢

70分代码，还能继续优化吗

楼主把记忆化加上，DFS就不会超时了但无论怎么说，还是用一个二进制mask表示有哪些口味的糖果才是正解，M不超过20的数据规模几乎是在求着你用二进制了

楼主可以试试状压加bfs 把每个品种转为位掩码看作是一个节点，全部入队，跑一边bfs就行了 状压dp感觉时间挺极限的

虽然写的是递归，但我测试过了，洛谷P8687，能全部Accept

简述一下思路
1. 因为糖果的口味数不超过20，所以用一个uint32_t来表示状态，这也是所谓状压DP中的状压，即状态压缩，对于每一包糖果，如果它包含口味i，则第i-1位置为1(口味从1-N，对应的位从0到N-1)，代码中的final_state为0到N-1位全置为1，也就是要覆盖所有口味的意思。糖果包的信息存储于candy_info[100]中
2. DP，方程为 F(i, j) = min(F(i-1,Q) + 1, F(i-1, j))
其中F(i, j)表示，使用所有标号不超过i的糖果包(这里一共有i+1包)，要达到状态j，至少需要几包
这里Q是一个集合相减结果状态，就是j状态对应所有的口味，对candy_info[i]对应的所有口味做一个集合减法(留下属于前者但不属于后者的元素)，以状态位来表示如下
Q = j & (~candy_info[i])
这个状态转移的理解方式是，如果F(i,j)达到最少包数时，不使用第i包，那么它就相当于F(i-1, j)，如果使用第i包，那该使用方法的其他糖果包一定能覆盖Q，再加上1包(第i包)则能覆盖j
3. 考虑到如果Q = j，则min值一定为后者，不必进行2项展开。因为根据题目数据范围，j最多为20位，所以如果Q != j，则Q至少要比j少1为，所以进行两项展开的层数不会超过20层。
4, i == 0和j == 0均为递归终止条件，其中j = 0表示不需要覆盖任何口味，所以0包即可完成, i = 0表示只用第0包糖果能否覆盖状态j，可以简单计算。
5. 以递归形式实现，为了防止重复计算，使用一个大数组dp[][]存储计算过的结果，i不超过100，j不超过2^20，因为F(i, j)的值不超过20，所以可以用unsigned char存储。计算F(i, j)时先查表，如果找不到再计算，算完存表。