学习笔记 - LeetCode526 优美的排列
仅以此笔记祭奠我逝去的十几根头发。
我把每一篇(第一页)题解都完完整整地读了三遍以上，唯一能看懂一点点的一篇是这个。
https://leetcode-cn.com/problems/beautiful-arrangement/solution/yi-ti-wu-jie-dfs-bao-sou-ji-yi-hua-dp-zh-qblw/
作者通过几个步骤从DFS过渡到了动态规划。
然后算是对动态规划有了初步的认识......就基于这篇题解写一些自己的理解吧。
深度优先搜索我是没有想到的，我自己先是用字典序写了，然后在看了八皇后问题以后，用回溯解决了。写完发现我的回溯和别人有点不一样，要慢很多......原因应该是我没用递归，导致需要记录已经填入的数字的顺序。
然后是题解里面的深度优先搜索，我看了太多遍题解然后自己写的，已经分不清是记住代码以后照着抄的，还是自己真的学会了DFS......总之DFS要比我的回溯快很多。
没什么好说的，唯一需要注意的点是，这里用了一个boolean数组来记录已经用过的数字。
就是说对于后面的位置而言，只需要关心前面用了哪些数字，不用管前面的数字是怎么排列的。我那个回溯需要记录顺序是因为没用递归的写法，为了避免某一位重复填入某个数字，必须要记录。
然后是状态压缩，我自己没写就直接CV过来了：
就是把那个boolean数组变成了一个int类型，用二进制位来表示用过的数字，假设二进制的第i位为1就说明i+1这个数字用过了。
题解的说法是，因为n<=15，所以可以用一个int的二进制表示。
这个因果关系没问题，但我还是不知道为什么它们可以想到用二进制来表示......假设不知道状态压缩这个词，我绝对想不到可以用二进制来表示。
然后是加了记忆化的DFS：
根据题解作者的说法，“有可能重复计算【相同的 i，相同的 visited】，所以加上记忆化”......这句话我有点没看懂，所以慢慢想一下：
i代表当前的位数，visited代表哪些数已经被使用了。也就是说，给某一位填写不同数字时，会有相同的数的使用情况，当相同的情况出现时，用已经记录好的答案。
这么说还是不清楚。首先理清一件事，深度优先搜索里，count记录的是什么......
每一次递归都会把位数往后推一位，然后每次返回的都是某种数使用情况下，当前的位数到最后一位，一共有多少种排列。比如N=7，然后前两位确定是1 2，这种情况下，i=3的这一次的调用，返回值就是排除了1 2 这两个数字以后，从第三位到最后一位有多少种排列。
记忆化会记录下1 2被使用的同时，第三位到最后一位的排列数。
然后关键的部分来了，当前面的排列变成2 1 时，这个记录可以直接拿来用。
我有点蠢了，这个想了很久才明白：不管前面填的1 2 还是 2 1 ，第三位开始到最后一位的排列数是不变的。
重要的还是前面说的，对于某一位而言，它只关心前面用了哪些数字，并不关心前面的排列顺序......这样想就可以变成一个子问题：在除去某些数字的情况下，i-N之间的排列数。
然后这个子问题的答案可以重复使用——其实已经有点动态规划的意思了。
带着这种想法再看代码，就很好理解了。memo的第一个维度是位数，第二个维度是数的使用情况，存储的值是某种“数使用情况”下，某一位到最后一位的排列数。
第二个维度的大小要给2的n+1次方-1，因为使用二进制记录使用情况的话，最多就是15个数全用，也就是15个1。n=15的话，2的n+1次方等同于1左移15位，也就是1后面15个0，减1就是15个1。
总之，这一步我想了好久才明白，能写出来的话应该差不多理解了。
然后进入正题，动态规划。
这个代码有八成是凭记忆写的，并不算真的理解了......然后题解里面说从记忆化过度到DP很简单，可能是刚刚接触DP的缘故，我感觉前面的记忆化和DP完全不一样，或者完全相反。
虽然都有一样的一个二维数组，但记忆化的那个数组存储的是某种“数使用情况”下，某一位到最后一位的所有排列，是从后往前算的。而DP的这个数组，存储的是某种“数使用情况”下，所有的排列，是从前往后算的。
而且记忆化里面的status，存的是已经用过的数字，目的是不再用这些数；DP正好相反，是从status里面找出数字填上。
除此以外，对于动态规划我还是有一些疑问。
什么是状态？
在这一题里，状态是"数的使用情况"，但是如果到了别的题目呢......看了很多教程，并没有说状态是什么，仅仅只是说要声明一个数组，然后确定数组的意义。
这种偏哲学的问题先放着，先看代码。不谈动态规划，只说代码的意义的话......
枚举每一位上，所有的“数使用情况”，然后从可用的数里面找一个可以填在当前位上的，找到了就把这个数字去掉，看看剩下的数字在前面的位置一共有多少种排列，然后把排列数加在当前数使用状态下的排列数上......
很抽象说实话。对我来说，这么想会简单一点：动态规划是把问题分成子问题，然后把子问题的答案作为原来问题的输入。
对于这一题来说，分解出的子问题就是：从1-N里面拿i个数，填在前i位，能有多少种符合条件的排列。记住排列的数量，当i增加时，从前面记住的数量里算出i增加后排列的数量。
形象一点，当i=3，数的使用状态是1 2 3 的时候，代表1 2 3 放在前三位，能有多少种排列。然后当i=4，无论第4位填哪个数字，只要它用到了1 2 3 这三个数，并且没有填到第4位，那它和前三位搭配能有的排列数量都是一样的，而那个数量已经被记录下来了，直接加上就行了。当i=5，重复这个循环......
当N==i时，就是最终问题的答案。
我感觉自己差不多理解了，但是好难用语言描述清楚......
算了，直接看最终的代码，和官方的一模一样，算是标准答案了。
在我的机器上甚至不要1ms就能算出来，对比一下我那个回溯的80ms，简直丧心病狂。
去掉了i的维度。i是当前在给第几位填数字，这个值通过status可以算出来，所以不需要i了。
但我自己还是有一些疑问：有i的话，保证了在给后面的位置填数字是，一定可以得到前面位置的排列数，去掉这个i还能保证这一点吗。
比如，N=15，就有1到15这些数可以填在第一位的情况，这样无论第二位填几，都可以从第一位得到排列数。但是没有i的话，随着status增长，并不会优先把第一位的所有情况列出来。
譬如，status=3的话，二进制就是0 1 1 ，是 1 2 被使用了的情况。
好像还是可以的。0 1 1 之前已经有了 0 0 1和 0 1 0的情况......
至于为什么可以，应该是利用了二进制的特性：所有数都可以视为更小的数的组合。
比如，5这个数就是4和1的组合。然后在status=5以前，一定有status=4和status=1......
好，到这里这一题差不多就算是完成了。从最开始觉得完全做不了，到看到官方题解后的一脸懵逼，到现在稍微能理解一点点......多少算是有一些进步吧。
是我的视野过于狭隘了，因为题目说了排列，我就总是想着去枚举排列......其实换一个思路，既然题目没有说要具体的排列方式，完全可以不去真正把排列列举出来。
两个月整的时间就做了一道题，还是随手点进去的题目.....虽然不是每天都在想，但还是花了挺多心思的，看着速度越来越快，就很爽。
学会了回溯，对记忆化搜索，DFS，动态规划有了初步的认识......还行。
