本題要使用 DP 來做，所以先我們把規律整理好。

河內塔的規律

1. 由於大盤絕不在小盤上面的關係，所以每一柱都會是排序好的，只是中間會有空缺。

2. 當你要將一個高度為 n 的塔完整地從 A 柱移動至 B 柱時的最少步驟必為 2ⁿ - 1
   Ex: 移動高度為 3 的塔

   零　　　　一　　　　二　　　三　　　　四　　　　五　　　　六　　　七
   1 x x 　　 x x x 　　 x x x 　　 x x x 　　 x x x 　　 x x x 　　 x x x 　　 x 1 x
   2 x x 　　 2 x x 　　 x x x 　　 x x 1 　　 x x 1 　　 x x x 　　 x 2 x 　　 x 2 x
   3 x x 　　 3 1 x 　　 3 1 2 　　 3 x 2 　　 x 3 2 　　 1 3 2 　　 1 3 x 　　 x 3 x

   會是 2ⁿ-1 是因為每要移動高度為 n 的塔，都必須先把高度為 n-1 的塔搬開，移動盤子 n，再把搬開的 n-1 塔般回 n 上，而要移動盤子 n-1 又要移動 n-2 塔…以此類推直到 n 為盤子 1 時，移動他只需要一步(上面沒有盤子了)，接者再逆推回去
   n = 2 塔：[塔 1] + 1 + [塔 1] = 1 + 1 + 1 = 3、
   n = 3 塔：[塔 2] + 1 + [塔 2] = 3 + 1 + 3 = 7、
   n = 4 塔：[塔 3] + 1 + [塔 3] = 7 + 1 + 7 = 15、
   之後以此類推 ([]為移動該塔的步驟數)
   然後就能發現 塔 n = 2^n-1 * 2 + 1 也就等於 2ⁿ - 1。

3. 想移動下面的盤子一定要先把上面的盤子都移開，所以最下面的盤子一定是最後一個動的。

4. 因為河內塔只有三根柱子、且大盤不能放到小盤上，所以如果你要把第 n 盤從 A 柱移動到 B 柱時，那你就必須要把所有比 n 還小的盤子都放到 C 柱上，換句話說，所有比 n 小的盤子都必須要移動到不是盤子 n 原本的柱或目標柱(也就是剩下的那柱)，而如果 n 原本的柱子就是目標柱，那就要把比 n 小的盤子堆到 n 所在的柱子上，維持塔的完整性，這樣之後下面的盤子才動的了。

5. 承 1 和 4，既然已經排序好、且比 n 小的都在 C 柱上，那 C 柱就一定會有一個 n-1 的子塔(從 n-1 ~ 1，排好、且中間無空缺的塔)

規律分析

1. 因為最下面的最後才能動，所以 DP 要由上而下

2. 每要移動 n 就會把 n 以上的盤子堆成一座 n-1 的子塔

3. 隨著不斷的 DP，要移動的就越底層，子塔就會越高

4. n 子塔的位子要在 不是 n+1 盤子的位子或目的地的最後一處，如果盤子的位置和目的地相同，那 n 子塔則也要和他們在相同位子，這裡有個技巧，用如果用 1,2,3 來表示柱子，這時候

   [n 子塔的位子] = 6 - [n-1 盤當前位子] - [n-1 盤目標位子]

   至於原因…因為 1 + 2 + 3 = 6，所以 6 減任意兩數(柱)就必然會剩下最後一個沒被用到的數(柱)，而當 6 - 2 - 2 時輸出為 2，一樣符合條件，不過 當前位子 = 目標位子 的情況在實作時都會在前面被過濾掉就是了。

5. 所以 DP 要做的就是從底部開始找出每層的目標位置，再從頂部開始把每層移動至目標位置 (子塔會在配合移動時越建越高，最後高度必是底部 - 1 ~ 1)。

到此為止是快速求出混亂河內塔還原回一個完整塔所需步驟的方法，但根據題目的目標也可能是混亂的，所以排好之後又要打亂，但好消息是打亂遠比還原輕鬆得多，從底部開始，如果”盤 n”的目標柱跟當前柱不一樣，就把”塔 n-1”搬到剩下的柱，把”盤 n”移至目標位置，如此反覆直到最頂層即可。

一些雜項

1. 本題 DP 的其實就是這 4 個部分 : 做好的子塔的高度和位置、要移動的盤子的初始位置和目標位置，然後從上到下排好、再從下到上放到目標位置。

2. 從頂層開始起始陣列有可能會連續好幾個一樣
   Ex:

   1 x x
   2 x x
   3 x x
   x 4 x
   x x 5

   這時候直接把 3 開始當子塔可以省掉一些判斷時間。

3. 從底部開始陣列有可能起始位置 = 目標位置，這些都是不用排的，一樣可以在開始過濾掉。

4. 雖然上面多次提到要移動子塔，但由於子塔一定只會在某一柱上，所以不用真的把陣列的元素都改到子塔位置，用一個元素代表子塔位置即可。

5. 河內塔邏輯比較複雜，多用紙筆模擬幾次情境會比較好理解上述的規律和流程。