Dynamic Programming

DP 是什麼? Dynamic是“動態的” DP中文叫做“動態規劃” 類似遞迴的寫作方式 基本概念就是建表 用舊的資料表格求出新的資料，將新的資料放入表格中，再用該表格求更新的資料。 DP會將跑出來的資料儲存，遞回不會儲存資料。

DP 怎麼做? 實做DP的時候，就像我們前面說的，首先會建立一個table來儲存跑出來的資料。 我們要利用先前的小資料求之後的大資料。 Table Element Definition很重要的一點就是定義好資料的存放方式及位置，使的我們需要的時候更容易找到想要的資料。 好的Table更能讓coding變簡單，並減少空間浪費。

再講下去連我都睡著了… 所以直接來個例子吧

DP 的應用 - 費氏數列 0 1 1 2 3 5 8 13…很眼熟吧 費氏數列定義： 第n項 = n-1項+n-2項 寫成運算式就是： f(n) = f(n-1) + f(n-2) f(0) = 0; f(1) = 1; 之前遞迴也有用到這個舉例，現在可以用這個題目看看遞迴跟DP的不同。

DP 的應用 - 費氏數列 大家還記得遞迴吧?遞迴的作法是： 那DP呢? f(10) = f(9)+f(8)….執行f(9)跟f(8) f(2)=f(1)+f(0)…f(2) = 1 存入table f(3)=f(2)+f(1)…f(3) = 2 存入table …DP則是由f(0)開始往上找的

DP 費氏數列過程實做 1 5 8 13 21 f(0) =0; f(1) =1; f(2) = f(1)+f(0) = 1 + 0 = 1 1 5 8 13 21 f(0) =0; f(1) =1; f(2) = f(1)+f(0) = 1 + 0 = 1 f(3) = f(2)+f(1) = 1 + 1 = 2 f(4) = f(3)+f(2) = 2 + 1 = 3 … f(9) = f(8)+f(7) = 21 + 13 = 34 f(10) = f(9)+f(8) = 34 + 21 = 55

DP 優點 - 執行效率 剛剛的f(10)執行完之後 我們接著想求f(6)跟f(11)… 5 8 13 21 34 55 8 f(6) = 89

DP V.S. 遞迴 遞迴是由上往下(top-down)的思考方式 遞迴的優點： 遞迴的缺點： 節省記憶體空間，想法比較簡單 不斷呼叫自己的作法相當花時間，每次都要從頭執行 呼叫自己的時候會使用到stack memory，若呼叫太多次stack memory滿了，就會出現錯誤

DP V.S. 遞迴 DP是由下而上(bottom-up)的方法。 DP的優點： DP的缺點： 執行效率比遞迴好!! 若題目沒有先給定最大範圍就無法預先建表 如果題目給的範圍太大記憶體不足也無法處理 過程的思考比較困難

DP 應用的重點!!! 計算順序很重要： 因為也會用到迴圈，所以要設定好起始值跟終止條件。 為了求出之後需要的大資料我們一定要先算出之前的小資料，在依序往上做。 因為也會用到迴圈，所以要設定好起始值跟終止條件。 記得要運用到table所存取的資料，不要每次都從頭做起，否則就失去DP的意義了。

比較完了優缺點 趕緊再來看個例子囉!!

DP 的應用 - Tiling Tiling，就是堆積木。題目給了一些指定大小形狀的積木，然後問要組成指定大小形狀的圖形有幾種作法。 這裡用ACM10359為例子。 題目： 你現在有以下的積木，要組出2*n的圖形，有幾種排法?

DP 的應用 - Tiling 什麼意思??舉個例子吧： 當n=1 只有一種→ n=2 有三種→ n=3 有五種→

DP 的應用 – Tiling 我們現在要拼成2*n的積木 我們可以往下討論，2*n的積木要用2*(n-1)的積木跟哪些其他的積木組成呢?? 答案很明顯是：

DP 的應用 – Tiling 接下來討論2*(n-2)： 所以2*(n-2)總共有兩組新的 那2*(n-3)呢?

DP 的應用 – Tiling 2*(n-4)，2*(n-5)…等狀況都會在2*(n-1)和2*(n-2)中討論了，所以我們需要討論的就是以下三種狀況： 所以我們得到公式： F(n) = F(n-1) + 2*F(n-2) 只要使用這個公式就可以求出我們要的2*n的排法了!!

DP 的應用 - LIS LIS = Longest Increasing Subsequence 中國人都叫他“最長遞增部分序列” 1 4 6 10 22 45 這就是一個遞增序列 1 13 24 5 7 9 這就不是一個遞增序列，但它其中有1 5 7 9存在。 題目通常會任意給一個字串，我們要從中找出最長的遞增部分序列及長度。

DP 的應用 - LIS N 1 2 3 4 5 6 7 8 Data[n] 9 12 25 33 length

DP 的應用 - LIS N 1 2 3 4 5 6 7 8 Data[n] 9 12 25 33 length

DP 的應用 - LIS N 1 2 3 4 5 6 7 8 Data[n] 9 12 25 33 length

DP 的應用 - LIS N 1 2 3 4 5 6 7 8 Data[n] 9 12 25 33 length

DP 的應用 - LIS N 1 2 3 4 5 6 7 8 Data[n] 9 12 25 33 length

DP 的應用 - LIS N 1 2 3 4 5 6 7 8 Data[n] 12 25 33 length

DP 的應用 - LIS N 1 2 3 4 5 6 7 8 Data[n] 9 12 25 33 length

DP 的應用 - LIS N 1 2 3 4 5 6 7 8 Data[n] 9 12 25 33 length

DP 的應用 - LIS N 1 2 3 4 5 6 7 8 Data[n] 9 12 25 33 length

DP 的應用 - LIS N 1 2 3 4 5 6 7 8 Data[n] 9 12 25 33 length 1 2 3 4 5 6 7 8 Data[n] 9 12 25 33 length 所以我們得知最暢遞增部分序列的長度就是6

DP 的應用 - LIS 那我們要怎麼找這個LIS長怎樣呢? N 1 2 3 4 5 6 7 8 Data[n] 9 12 25 33 1 2 3 4 5 6 7 8 Data[n] 9 12 25 33 length 方法：建立一個長度同剛剛算出來的LIS的陣列，然後從最後開始往前跑。 從length=6的8開始往回找，每次找到後，目標的length就減一。 從右邊開始用這種遞減的方式把資料存入陣列中。

DP 的應用 - LIS N 1 2 3 4 5 6 7 8 Data[n] 9 12 25 33 length N+1 1 2 3 4 5 1 2 3 4 5 6 7 8 Data[n] 9 12 25 33 length N+1 1 2 3 4 5 6 LIS[n] 7 9 12 25 33

練習題 費氏數列(需用大數) 495 堆積木(需用大數) 10359 10918 LIS 497