LeetCode 691. 贴纸拼词

我们有 n 种不同的贴纸。每个贴纸上都有一个小写的英文单词。

您想要拼写出给定的字符串 target ，方法是从收集的贴纸中切割单个字母并重新排列它们。如果你愿意，你可以多次使用每个贴纸，每个贴纸的数量是无限的。

返回你需要拼出 target 的最小贴纸数量。如果任务不可能，则返回 -1 。

注意：在所有的测试用例中，所有的单词都是从 1000 个最常见的美国英语单词中随机选择的，并且 target 被选择为两个随机单词的连接。

动态规划，状态压缩，记忆化搜索......其实这些东西我应该是掌握了的，我以为自己已经通过上次的题目掌握了，结果到需要用的时候还是......

分析一下原因吧，还是因为没有理解动态规划的本质，只会复读什么“分解成子问题”。

根本的根本问题是，抽象思维能力差太多。哪怕看了官方题解，还是有一堆问题：

首先最大的问题是，所有给res赋值的语句里，没有值低于m+1的，但是为什么最后还是能够返回那么小的值，那些值是从哪来的......

很神奇吧，没有任何一条语句给res赋值3，但是最后它就是可以等于3。

直接说结论：res的值是从memo[0]获取的。

假设可以拼出来，那么第一次真正有返回值的回调，mask一定是全0，也就是memo[0]=0。

或者说的专业一点，res的值是由状态memo[0]转移而来的。

程序是过程，是动态的，而我总是用静态的方法去思考，所以像个傻逼。对于简单的问题，确实可以这样，但过于抽象的问题就必须以动态的思维来看。

......

其实细节部分诸如位运算，还有if的条件之类的，很好理解，我真正觉得难以理解的是整体的思维。或者说，该怎么去思考一个问题......

分解成子问题，我也会这样想，也想到了状态压缩，但是真正去把这些东西优雅地组合起来解决问题，脑子就乱了。如果题目改成每次只能从贴纸中选一个字母，那我大概就行了，就是单纯地复杂了一个维度，我就很难把这个新的维度和已有的解题思路组合起来。

对于这题而言，我一直是存在误区的：

1. 从贴纸中寻找多个字符，或者单个字符，其实是同一个问题，但是我从来没有这么想过。我想到了算target和贴纸的重合部分，但是我是这么想的：寻找单个字符循环一次，寻找两个再循环，三个再循环，直接找不到，选出最大重合部分的贴纸，再寻找剩下的部分。

   这种时候动态规划的优势是，可以让人头脑清晰。我按自己的思路很快就被一堆乱七八糟的东西堵住了，但动态规划提供了一个可靠的框架，只要在框架里搭上正确的积木就行。

   还是那个问题，我的思维依旧不够抽象。

2. 贴纸的字符的顺序是可以不去关心的。因为要算重合部分，我就觉得贴纸的字符的顺序也必须要和target一样。

   但其实没有，根本不用去在意顺序，真正应该关心的是一张贴纸里能够找到的和target相同的字符数量，顺序无关紧要，我没有意识到这一点，所以想不出来。

   所以我还缺少看透问题本质的能力。

3. 留空。可能是递归写的少了，我完全不习惯先把返回值交给下一次调用这个思考方式，要让这个函数能够适配每一次的调用还要在最后返回正确的结果，该怎么做完全是空白。、

总结：四天没想出结果直接看了题解，下次遇到一样的问题大概还是没有头绪。

但至少总结出了一些方向，不算完全没有价值。