Dynamic Programming.

Presentation on theme: "Dynamic Programming."— Presentation transcript:

1 Dynamic Programming

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

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

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

5 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的不同。

6 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)開始往上找的

7 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 f(3) = f(2)+f(1) = = 2 f(4) = f(3)+f(2) = = 3 … f(9) = f(8)+f(7) = = 34 f(10) = f(9)+f(8) = = 55

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

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

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

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

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

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

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

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

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

17 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的排法了!!

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

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

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

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

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

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

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

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

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

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

28 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

29 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就減一。 從右邊開始用這種遞減的方式把資料存入陣列中。

30 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

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