随手写

做dp问题时 不管多么复杂的题目一定要牢记状态转移!!!! 正是因为状态转移才能够降低爆搜的时间复杂度
就类似于棋盘问题 使用dfs的时间复杂度高的原因就是 放置了一个棋子之后 它会去遍历后面所有放置棋子的情况 然后再递归回来 放置第二个棋子之后又去遍历后面所有放置棋子的方案

而使用dp优化就是 放完一个棋子之后放置第二个棋子(每次只保存前面放置棋子的最优值) 然后放置后面的棋子的时候并不需要考虑前面单独的棋子如何放置 而是考虑整个最值的情况(f[i][j] … )

而使用记忆化搜索优化的话 它优化的是后面放置棋子的状态 例如爆搜它放置完一个棋子之后就会遍历后面所有棋子的状态 在它遍历后面的状态的时候就用一个数组来记录后面状态的最值(同样是最值!!!) 然后递归放置第二个棋子的时候它就直接查表找最值即可

例如 1052设计密码：里面使用到了复杂的KMP 但是使用它的目的就是为了能够拆分dp的状态 让它能够通过前面状态转移到后面的状态
其中 f[i] 表示考虑构造前i个字母的总方案数 这样每次考虑第i个字母的时候只需要考虑f[i-1]即可(f[i-1]代表了前面所有的方案) 那么如何通过前面计算出来的状态转移过来 就需要使用到一定的技巧(KMP匹配 + 自动机)

关于具体是如何使用KMP + 自动机 拆分状态的目前还没弄太明白 等以后回头再想