僅以此筆記祭奠我逝去的十幾根頭發(fā)。

我把每一篇(第一頁(yè))題解都完完整整地讀了三遍以上，唯一能看懂一點(diǎn)點(diǎn)的一篇是這個(gè)。

https://leetcode-cn.com/problems/beautiful-arrangement/solution/yi-ti-wu-jie-dfs-bao-sou-ji-yi-hua-dp-zh-qblw/

作者通過(guò)幾個(gè)步驟從DFS過(guò)渡到了動(dòng)態(tài)規(guī)劃。

然后算是對(duì)動(dòng)態(tài)規(guī)劃有了初步的認(rèn)識(shí)......就基于這篇題解寫(xiě)一些自己的理解吧。

深度優(yōu)先搜索我是沒(méi)有想到的，我自己先是用字典序?qū)懥?，然后在看了八皇后?wèn)題以后，用回溯解決了。寫(xiě)完發(fā)現(xiàn)我的回溯和別人有點(diǎn)不一樣，要慢很多......原因應(yīng)該是我沒(méi)用遞歸，導(dǎo)致需要記錄已經(jīng)填入的數(shù)字的順序。

然后是題解里面的深度優(yōu)先搜索，我看了太多遍題解然后自己寫(xiě)的，已經(jīng)分不清是記住代碼以后照著抄的，還是自己真的學(xué)會(huì)了DFS......總之DFS要比我的回溯快很多。

沒(méi)什么好說(shuō)的，唯一需要注意的點(diǎn)是，這里用了一個(gè)boolean數(shù)組來(lái)記錄已經(jīng)用過(guò)的數(shù)字。

就是說(shuō)對(duì)于后面的位置而言，只需要關(guān)心前面用了哪些數(shù)字，不用管前面的數(shù)字是怎么排列的。我那個(gè)回溯需要記錄順序是因?yàn)闆](méi)用遞歸的寫(xiě)法，為了避免某一位重復(fù)填入某個(gè)數(shù)字，必須要記錄。

然后是狀態(tài)壓縮，我自己沒(méi)寫(xiě)就直接CV過(guò)來(lái)了：

就是把那個(gè)boolean數(shù)組變成了一個(gè)int類型，用二進(jìn)制位來(lái)表示用過(guò)的數(shù)字，假設(shè)二進(jìn)制的第i位為1就說(shuō)明i+1這個(gè)數(shù)字用過(guò)了。

題解的說(shuō)法是，因?yàn)閚<=15，所以可以用一個(gè)int的二進(jìn)制表示。

這個(gè)因果關(guān)系沒(méi)問(wèn)題，但我還是不知道為什么它們可以想到用二進(jìn)制來(lái)表示......假設(shè)不知道狀態(tài)壓縮這個(gè)詞，我絕對(duì)想不到可以用二進(jìn)制來(lái)表示。

然后是加了記憶化的DFS：

根據(jù)題解作者的說(shuō)法，“有可能重復(fù)計(jì)算【相同的 i，相同的 visited】，所以加上記憶化”......這句話我有點(diǎn)沒(méi)看懂，所以慢慢想一下：

i代表當(dāng)前的位數(shù)，visited代表哪些數(shù)已經(jīng)被使用了。也就是說(shuō)，給某一位填寫(xiě)不同數(shù)字時(shí)，會(huì)有相同的數(shù)的使用情況，當(dāng)相同的情況出現(xiàn)時(shí)，用已經(jīng)記錄好的答案。

這么說(shuō)還是不清楚。首先理清一件事，深度優(yōu)先搜索里，count記錄的是什么......

每一次遞歸都會(huì)把位數(shù)往后推一位，然后每次返回的都是某種數(shù)使用情況下，當(dāng)前的位數(shù)到最后一位，一共有多少種排列。比如N=7，然后前兩位確定是1 2，這種情況下，i=3的這一次的調(diào)用，返回值就是排除了1 2 這兩個(gè)數(shù)字以后，從第三位到最后一位有多少種排列。

記憶化會(huì)記錄下1 2被使用的同時(shí)，第三位到最后一位的排列數(shù)。

然后關(guān)鍵的部分來(lái)了，當(dāng)前面的排列變成2 1 時(shí)，這個(gè)記錄可以直接拿來(lái)用。

我有點(diǎn)蠢了，這個(gè)想了很久才明白：不管前面填的1 2 還是 2 1 ，第三位開(kāi)始到最后一位的排列數(shù)是不變的。

重要的還是前面說(shuō)的，對(duì)于某一位而言，它只關(guān)心前面用了哪些數(shù)字，并不關(guān)心前面的排列順序......這樣想就可以變成一個(gè)子問(wèn)題：在除去某些數(shù)字的情況下，i-N之間的排列數(shù)。

然后這個(gè)子問(wèn)題的答案可以重復(fù)使用——其實(shí)已經(jīng)有點(diǎn)動(dòng)態(tài)規(guī)劃的意思了。

帶著這種想法再看代碼，就很好理解了。memo的第一個(gè)維度是位數(shù)，第二個(gè)維度是數(shù)的使用情況，存儲(chǔ)的值是某種“數(shù)使用情況”下，某一位到最后一位的排列數(shù)。

第二個(gè)維度的大小要給2的n+1次方-1，因?yàn)槭褂枚M(jìn)制記錄使用情況的話，最多就是15個(gè)數(shù)全用，也就是15個(gè)1。n=15的話，2的n+1次方等同于1左移15位，也就是1后面15個(gè)0，減1就是15個(gè)1。

總之，這一步我想了好久才明白，能寫(xiě)出來(lái)的話應(yīng)該差不多理解了。

然后進(jìn)入正題，動(dòng)態(tài)規(guī)劃。

這個(gè)代碼有八成是憑記憶寫(xiě)的，并不算真的理解了......然后題解里面說(shuō)從記憶化過(guò)度到DP很簡(jiǎn)單，可能是剛剛接觸DP的緣故，我感覺(jué)前面的記憶化和DP完全不一樣，或者完全相反。

雖然都有一樣的一個(gè)二維數(shù)組，但記憶化的那個(gè)數(shù)組存儲(chǔ)的是某種“數(shù)使用情況”下，某一位到最后一位的所有排列，是從后往前算的。而DP的這個(gè)數(shù)組，存儲(chǔ)的是某種“數(shù)使用情況”下，所有的排列，是從前往后算的。

而且記憶化里面的status，存的是已經(jīng)用過(guò)的數(shù)字，目的是不再用這些數(shù)；DP正好相反，是從status里面找出數(shù)字填上。

除此以外，對(duì)于動(dòng)態(tài)規(guī)劃我還是有一些疑問(wèn)。

什么是狀態(tài)？

在這一題里，狀態(tài)是"數(shù)的使用情況"，但是如果到了別的題目呢......看了很多教程，并沒(méi)有說(shuō)狀態(tài)是什么，僅僅只是說(shuō)要聲明一個(gè)數(shù)組，然后確定數(shù)組的意義。

這種偏哲學(xué)的問(wèn)題先放著，先看代碼。不談動(dòng)態(tài)規(guī)劃，只說(shuō)代碼的意義的話......

枚舉每一位上，所有的“數(shù)使用情況”，然后從可用的數(shù)里面找一個(gè)可以填在當(dāng)前位上的，找到了就把這個(gè)數(shù)字去掉，看看剩下的數(shù)字在前面的位置一共有多少種排列，然后把排列數(shù)加在當(dāng)前數(shù)使用狀態(tài)下的排列數(shù)上......

很抽象說(shuō)實(shí)話。對(duì)我來(lái)說(shuō)，這么想會(huì)簡(jiǎn)單一點(diǎn)：動(dòng)態(tài)規(guī)劃是把問(wèn)題分成子問(wèn)題，然后把子問(wèn)題的答案作為原來(lái)問(wèn)題的輸入。

對(duì)于這一題來(lái)說(shuō)，分解出的子問(wèn)題就是：從1-N里面拿i個(gè)數(shù)，填在前i位，能有多少種符合條件的排列。記住排列的數(shù)量，當(dāng)i增加時(shí)，從前面記住的數(shù)量里算出i增加后排列的數(shù)量。

形象一點(diǎn)，當(dāng)i=3，數(shù)的使用狀態(tài)是1 2 3 的時(shí)候，代表1 2 3 放在前三位，能有多少種排列。然后當(dāng)i=4，無(wú)論第4位填哪個(gè)數(shù)字，只要它用到了1 2 3 這三個(gè)數(shù)，并且沒(méi)有填到第4位，那它和前三位搭配能有的排列數(shù)量都是一樣的，而那個(gè)數(shù)量已經(jīng)被記錄下來(lái)了，直接加上就行了。當(dāng)i=5，重復(fù)這個(gè)循環(huán)......

當(dāng)N==i時(shí)，就是最終問(wèn)題的答案。

我感覺(jué)自己差不多理解了，但是好難用語(yǔ)言描述清楚......

算了，直接看最終的代碼，和官方的一模一樣，算是標(biāo)準(zhǔn)答案了。

在我的機(jī)器上甚至不要1ms就能算出來(lái)，對(duì)比一下我那個(gè)回溯的80ms，簡(jiǎn)直喪心病狂。

去掉了i的維度。i是當(dāng)前在給第幾位填數(shù)字，這個(gè)值通過(guò)status可以算出來(lái)，所以不需要i了。

但我自己還是有一些疑問(wèn)：有i的話，保證了在給后面的位置填數(shù)字是，一定可以得到前面位置的排列數(shù)，去掉這個(gè)i還能保證這一點(diǎn)嗎。

比如，N=15，就有1到15這些數(shù)可以填在第一位的情況，這樣無(wú)論第二位填幾，都可以從第一位得到排列數(shù)。但是沒(méi)有i的話，隨著status增長(zhǎng)，并不會(huì)優(yōu)先把第一位的所有情況列出來(lái)。

譬如，status=3的話，二進(jìn)制就是0 1 1 ，是 1 2 被使用了的情況。

好像還是可以的。0 1 1 之前已經(jīng)有了 0 0 1和 0 1 0的情況......

至于為什么可以，應(yīng)該是利用了二進(jìn)制的特性：所有數(shù)都可以視為更小的數(shù)的組合。

比如，5這個(gè)數(shù)就是4和1的組合。然后在status=5以前，一定有status=4和status=1......

好，到這里這一題差不多就算是完成了。從最開(kāi)始覺(jué)得完全做不了，到看到官方題解后的一臉懵逼，到現(xiàn)在稍微能理解一點(diǎn)點(diǎn)......多少算是有一些進(jìn)步吧。

是我的視野過(guò)于狹隘了，因?yàn)轭}目說(shuō)了排列，我就總是想著去枚舉排列......其實(shí)換一個(gè)思路，既然題目沒(méi)有說(shuō)要具體的排列方式，完全可以不去真正把排列列舉出來(lái)。

兩個(gè)月整的時(shí)間就做了一道題，還是隨手點(diǎn)進(jìn)去的題目.....雖然不是每天都在想，但還是花了挺多心思的，看著速度越來(lái)越快，就很爽。

學(xué)會(huì)了回溯，對(duì)記憶化搜索，DFS，動(dòng)態(tài)規(guī)劃有了初步的認(rèn)識(shí)......還行。