動態規劃(Dynamic Programming)

動態規劃通常用於最佳化問題，若問題可以被切割成許多小問題，經由小問題被解決後，可以組合起來成為大問題的解，局部小問題的解可以組成大問題的解，稱作最佳子結構(Optimal Substructure)，動態規畫需要符合此特性。

這些小問題不斷的重複，浪費許多時間在計算重複的問題，這時就可以使用陣列儲存小問題的解，相同的小問題只需計算一次，可以快速從陣列中找尋小問題的解，避免重複計算，讓程式計算速度更快，稱作記憶化(Memoization)。

動態規劃的解題步驟

Step1)定義大問題與小問題的關係

大問題是由小問題所組合起來，而這些小問題不斷的重複，浪費許多時間在重複計算小問題的解，這時就可以使用陣列儲存小問題的解，大問題與小問題的關係，可以使用遞迴關係來表示，又稱作狀態轉移方程式。

Step2)使用陣列儲存小問題的解

須明確定義陣列的大小與維度，與每個維度所要擺放的資料，定義陣列的初始值，才可以使用Step1所定義的遞迴關係求出大問題的解。

Step3)是否需要找出最佳解路徑若需要最佳解的路徑，使用陣列紀錄解的過程，再印出最佳解的路徑。

(1)費氏數列

費氏數列是將第1項與第2項相加等於第3項，第2項與第3項相加等於第4項，依此類推，陣列可以儲存資料與使用索引值存取的特性，非常適合計算費氏數列，初始化費氏數列的第1項為1且第2項為1，請計算費氏數列前50項。

輸入說明

允許不斷輸入n，表示求第n項的費氏數列，n從1開始，表示費氏數列第1項。

輸出說明

輸出費氏數列第n項的值。

輸入範例

輸出範例

解題想法

使用陣列F計算費氏數列，且初始化F[0]=1，F[1]=1，當n大於等於2時，使用以下公式F[n]=F[n-1]+F[n-2]，也就是將陣列F的第n-1項加陣列F的第n-2項存入陣列F的第n項。

動態規劃的解題步驟

Step1)定義大問題與小問題的關係

費氏數列遞迴關係式為F[n]=F[n-1]+F[n-2]。

Step2) 使用陣列儲存小問題的解

陣列F計算費氏數列，且初始化F[0]=1，F[1]=1，當n大於等於2時，使用以下公式F[n]=F[n-1]+F[n-2]

Step3)本問題不需要找出最佳解的路徑。

程式碼

(2)01背包

(2-1)01背包 --不考慮最佳解路徑

假設有n個物品及一個背包，已知背包的負重能力與每個物品的價值與重量，物品只能取或不取，不能只取物品的一部分，且每樣物品只有一個，求在背包的負重能力範圍內放入背包所有物品的最大價值。

輸入說明

每次輸入數字n，n表示物品個數，n小於100，之後有n行每一行分別有兩個整數w與v，w表示物品的重量，而v表示物品的價值。最後輸入一個整數ks，表示背包的負重能力，且ks小於1000。

輸出說明

輸出一個整數，表示在背包的負重能力範圍內的放入背包所有物品的最大價值。

輸入範例

3 20

4 45

9 70

12 85

輸出範例

背包最大的價值為90

解題想法

依序考慮每個物品放或不放到背包，若放到背包後，形成更大的價值就放入背包中。

Step1)定義大問題與小問題的關係

依序考慮每個物品，目前考慮第i個物品是否要加入背包，假設有各種負重能力的背包，若負重小的背包加上第i個物品的價值大於負重大(負重小的背包負重重量加上第i個物品的重量)的背包但不放入第i個物品的價值，則將第i個物品加入背包更新負重大的背包價值，獲得負重大的背包問題的解。

Step2) 使用陣列儲存小問題的解

使用陣列k儲存各種背包負重重量的最大價值。

Step3)目前暫時不求最佳解的路徑。

程式碼

(2-2)01背包 --考慮最佳解路徑

假設有n個物品及一個背包，已知背包的負重能力與每個物品的價值與重量，物品只能取或不取，不能只取物品的一部分，且每樣物品只有一個，求在背包的負重能力範圍內放入背包所有物品的最大價值？須找出最佳解為何？

輸入說明

每次輸入數字n，n表示物品個數，n小於100，之後有n行分別是每一行兩個整數w與v，w表示物品的重量，而v表示物品的價值。最後輸入一個整數ks，表示背包的負重能力，且ks小於1000。

輸出說明

輸出一個整數，表示在背包的負重能力範圍內放入背包所有物品的最大價值，並輸出將那些物品放入背包獲得最大價值。

輸入範例

3 20

4 45

9 70

12 85

輸出範例

背包最大的價值為90

將第3個物品放入背包

將第1個物品放入背包

解題想法

依序考慮每個物品放或不放到背包，若放到背包中有更大的價值就放入背包中。

Step1)定義大問題與小問題的關係

Step2) 使用陣列儲存小問題的解

使用陣列k儲存各種背包負重重量的最大價值。

Step3)需使用另一個陣列p[i][j]，紀錄第i個物品，背包重量為j，是否選了第i個物品加入背包。

程式碼

(3) 換零錢

某個國家有n種硬幣面額，請你計算出達成目標金額x的最少硬幣個數，所輸入的n種硬幣面額一定可以達成目標金額x。

(3-1)換零錢—不考慮最佳解路徑

輸入說明

每次輸入數字n，n表示硬幣面額個數，n小於10，之後有n行每一行分別有一個整數v，表示硬幣的面額。最後輸入一個整數x，表示目標金額，且x小於50000。

輸出說明

輸出一個整數，表示達成目標金額x的最少硬幣個數。

輸入範例

輸出範例

解題想法

依序考慮每個面額的硬幣，利用「較小目標金額的硬幣個數」加1(使用正在考慮的硬幣一個)，與「較大目標金額(較小目標金額加上正在考慮硬幣面額)」的硬幣個數(表示不使用目前正在考慮的硬幣)，兩者之中較小的硬幣個數被保留下來。

Step1)定義大問題與小問題的關係

依序取出每個硬幣面額，假設目前考慮第i個硬幣，硬幣面額為v[i]，若「達成目標金額j，不使用第i個硬幣所需硬幣個數」大於「達成目標金額j-v[i]所需硬幣個數加1(使用v[i]硬幣一個)」，則使用第i個硬幣達成目標金額j，更新目標金額的硬幣個數為「目標金額j-v[i]所需硬幣個數加1」。

Step2) 使用陣列儲存小問題的解

使用陣列m儲存目標金額的最小硬幣數，初始化陣列m每個元素為很大的數，初始化陣列m第一個元素為0，表示目標金額0，需要0個硬幣。

Step3)目前暫時不求最佳解的路徑。

程式碼

(3-2) 換零錢—考慮最佳解路徑

輸入說明

每次輸入數字n，n表示硬幣面額個數，n小於10，之後有n行每一行分別有一個整數v，表示硬幣的面額。最後輸入一個整數x，表示目標金額，且x小於50000。

輸出說明

輸出一個整數，表示達成目標金額x的最少硬幣個數，接著一個個輸出組成目標金額x的硬幣面額。

輸入範例

輸出範例

9 9 1 1

解題想法

Step1)定義大問題與小問題的關係

Step2) 使用陣列儲存小問題的解

使用陣列m儲存目標金額的最小硬幣數，初始化陣列m每個元素為很大的數，初始化陣列m第一個元素為0，表示目標金額0，需要0個硬幣。

Step3)使用陣列p儲存達成目標金額的最後加入的硬幣面額，因而獲得較小的硬幣個數。

程式碼

(4)最長共同子序列(Longest Common Subsequence)

給定兩個英文字母的字串，請找這兩個英文字母字串的最長共同子序列(Longest Common Subsequence)，縮寫為LCS，兩個英文字母字串可以不取其中某些字元，但字母順序不能更換，大小寫英文字母視為不同字母。

(4-1)最長共同子序列—不考慮最佳解路徑

輸入說明

每次輸入兩英文字母字串，求這兩個英文字母字串的最長共同子序列，兩字串長度都不會超過100個字元。

輸出說明

輸出一個整數，表示這兩個英文字母字串的最長共同子序列長度。

輸入範例

comp

zope

輸出範例

解題想法

依序考慮兩字串的所有字母，找出最長共同子序列的長度。

Step1)定義大問題與小問題的關係

依序取出兩字串的每個字元，假設目前取出字串s1第i個字元，取出字串s2第j個字元，若字串s1第i個字元等於字串s2第j個字元，則目前最長共同子序列的長度增加1，否則目前最長共同子序列的長度為「字串s1從第0個字元取到第i-1個字元與字串s2從第0個字元取到第j個字元的最長共同子序列長度」與「字串s1從第0個字元取到第i個字元與字串s2從第0個字元取到第j-1個字元的最長共同子序列的長度」較大的長度，其中i為字串s1的索引值，從0開始到s1字串長度減1，j為字串s2的索引值，從0開始到s2字串長度減1。

Step2)使用陣列儲存最長共同子序列的長度。

使用陣列lcs儲存最長共同子序列的長度，lcs[i+1][j+1]用於儲存字串s1取第0到第i個字元，字串s2取第0到第j個字元的最長共同子序列的長度，其中i為字串s1的索引值，從0開始到s1字串的長度減1，j為字串s2的索引值，從0開始到s2字串的長度減1。初始化lcs[0][0]為0，表示兩空字串的最長共同子序列長度為0。

根據Step1、Step2與陣列lcs[i][j]的定義可以寫出以下程式。

Step3)目前暫時不求最佳解的路徑。

程式碼

(4-2)最長共同子序列—考慮最佳解路徑

輸入說明

每次輸入兩英文字母字串，求這兩個英文字母字串的最長共同子序列，兩字串長度都不會超過100個字元。

輸出說明

輸出一個整數，表示這兩個英文字母字串的最長共同子序列長度，接著輸出一個最長共同子序列的字串。

輸入範例

comp

zope

輸出範例

解題想法

依序考慮兩字串的所有字母，找出最長共同子序列的長度。

Step1)定義大問題與小問題的關係

依序取出兩字串的每個字元，假設目前取出字串s1第i個字元，取出字串s2第j個字元，若字串s1第i個字元等於字串s2第j個字元，則目前最長共同子序列的長度增加1，否則目前最長共同子序列的長度為「字串s1從第0個字元取到第i-1個字元與字串s2從第0個字元取到第j個字元的最長共同子序列長度」與「字串s1從第0個字元取到第i個字元與字串s2從第0個字元取到第j-1個字元的最長共同子序列長度」較大的長度，其中i為字串s1的索引值，從0開始到s1字串長度減1，j為字串s2的索引值，從0開始到s2字串長度減1。

Step2)使用陣列儲存最長共同子序列的長度。

使用陣列lcs儲存最長共同子序列的長度，lcs[i+1][j+1]用於儲存s1取第0到第i個字元，s2取第0到第j個字元的最長共同子序列的長度，其中i為字串s1的索引值，從0開始到s1字串長度減1，j為字串s2的索引值，從0開始到s2字串長度減1。初始化lcs[0][0]為0，表示兩空字串的最長共同子序列長度為0。

Step3)求最佳解的路徑。

使用陣列map[i][j]紀錄求最長共同子序列過程，若字串s1第i個字元等於字串s2第j個字元，則設定map[i+1][j+1]為3，否則若「字串s1從第0個字元取到第i個字元與字串s2從第0個字元取到第j+1個字元的最長共同子序列長度」大於「字串s1從第0個字元取到第i+1個字元與字串s2從第0個字元取到第j個字元的最長共同子序列長度」，則設定map[i+1][j+1]為1，否則設定map[i+1][j+1]為2，其中i為字串s1的索引值，從0開始，j為字串s2的索引值，從0開始，利用陣列map可以找出最長共同子序列。

根據Step1、Step2、Step3與陣列map[i][j]可以寫出以下程式。