一、動態規劃 (Dynamic programing, DP)：Slower
（一）概念
 |
| 動態規劃 slower |
題目給數個俄羅斯娃娃，計算俄羅斯娃娃最大連續可容納量，自己也算一個，每個娃娃不可以翻轉。上圖是比較慢的DP，概念上先製作一個Fite table，FitTable(x, y)代表x是否能容納？如果可以為1，如果不行為0。接下來再計算各娃娃的fit value和fitted value，fit value代表自己最大可容納量，fit value代表自己最大可被容納量。注意最大可容納量 (fit value) ≠ 最大連續可容納量 (maxFit)，可以看上圖左下的散佈圖，就知道為什麼不等於。
有了fit value和fitted value，就可以來製作DP table，即上圖的Ordered fitted map。DP表中的俄羅斯娃娃排序是依照fitted value由大到小，利用fit value = 0 -> maxF = 1 & fit value = 1 -> maxF = 2這兩個規則來初始化DP表，再依序去檢查下一個俄羅斯娃娃。
所以D, A, F會初始化為1, 2, 3，而E能容納D和F，則E maxFit = max(D maxFit, F maxFit) + 1；而C能容納A和D，則E maxFit = max(A maxFit, D maxFit) + 1；而B能容納A和D，則E maxFit = max(A maxFit, D maxFit) + 1。
最後可以得知B, C, E有最大連續可容納量，且我們不保證DP的最後一個值一定是最佳解，故在做DP時，就要隨時記錄現在的最大連續可容納量。
（二）實作
 |
| 用來協助DP的物件與函式 |
 |
| 動態規劃 slower 前處理與初始化 |
第一個步先製作fitTable，第二步計算fit和fitted，以及對DP表做初始化。
 |
| 動態規劃 slower 排序與執行DP |
第三步對DP表依照fittedValue遞減排序，由於fit, fitted, maxFit是存在unorderd_map fitValue，而unorderd_map是無法使用sort()，因為其iterator不是random，故必須將之放在一個可以排序的容器中，我使用vector且存放指向fitValue的iterator。儲存iterator有幾個好處是：
- 不用直接複製物件
- 可以享受unorderd_map的好處
最後針對orederFitValue執行後續的DP，並隨時紀錄現在最大的maxFit。
（三）時間複雜度
設俄羅斯娃娃數量為n，則這方法的時間複雜度為O(n^2)，但這方法仍太慢，會被LeetCode拒絕，因為做了2個多餘的處理。
- 計算fitTable
- 計算fit和fitted
這兩個步驟非常多餘。因為前者可以和執行DP一起合併，後者的fit也可以併在執行DP中，而後者的fitted可以用width或hight所取代。
利用width或hight直接對俄羅斯娃娃排序，雖然不能保證前者都是有較高的fitted，但可以保證兩件事情：
- 我能容納的俄羅斯娃娃都已經在前面初始化過了
- maxFit為1或2的娃娃都在前面
第一點保證是最為重要的，這使得DP的執行能夠順利，且能保證DP值為最大連續可容納量。如果用hight來排序俄羅斯娃娃，有可能第5個width比第2個width小，但第5個ㄖ不可能容納第2個，因此計算第5個maxFit並不會用到第2個值，因此能夠保證我能容納的俄羅斯娃娃都已經在前面初始化過這件事情。
由於width或hight排序能夠保證第一點，所以建立unorderd_map fitValue前，就可以先對俄羅斯娃娃做排序，自然設計上就會比較簡單。
二、動態規劃 (Dynamic programing, DP)：Faster
（一）概念
 |
| 動態規劃 faster |
第2版的DP就比第1版用到的表格還少，設計上就簡化許短，且程式碼與執行效能大大改善。可以看到我們一開始所建立的DP表早就是已經排序過的娃娃，所以可以不用使用關聯式容器（如：unorderd_map），可以使用一般的vector就好了，前一個方法會選擇使用關聯式容器是因為我希望我的key能跟著value一起移動。另外FitTable的計算可以直接合併在DP中，也可以發現FitTable的計算量直接砍半，因為排序能保證我後者的娃娃都是我無法容納的。
（二）實作
 |
| 動態規劃 faster 程式碼 |
留言
張貼留言