動態規劃(Dynamic Programming)
動態規劃(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項的值。
輸入範例
10
輸出範例
55
解題想法
使用陣列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。
輸出說明
輸出一個整數，表示在背包的負重能力範圍內的放入背包所有物品的最大價值。
輸入範例
4
3 20
4 45
9 70
12 85
12
輸出範例
背包最大的價值為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。
輸出說明
輸出一個整數，表示在背包的負重能力範圍內放入背包所有物品的最大價值，並輸出將那些物品放入背包獲得最大價值。
輸入範例
4
3 20
4 45
9 70
12 85
12
輸出範例
背包最大的價值為90
將第3個物品放入背包
將第1個物品放入背包
解題想法
依序考慮每個物品放或不放到背包，若放到背包中有更大的價值就放入背包中。
Step1)定義大問題與小問題的關係
依序考慮每個物品，目前考慮第i個物品是否要加入背包，假設有各種負重能力的背包，若負重小的背包加上第i個物品的價值大於負重大(負重小的背包負重重量加上第i個物品的重量)的背包但不放入第i個物品的價值，則將第i個物品加入背包更新負重大的背包價值，獲得負重大的背包問題的解。
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的最少硬幣個數。
輸入範例
4
4
1
9
13
20
輸出範例
4
解題想法
依序考慮每個面額的硬幣，利用「較小目標金額的硬幣個數」加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的硬幣面額。
輸入範例
4
4
1
9
13
20
輸出範例
4
9 9 1 1
解題想法
依序考慮每個面額的硬幣，利用「較小目標金額的硬幣個數」加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)使用陣列p儲存達成目標金額的最後加入的硬幣面額，因而獲得較小的硬幣個數。
程式碼
(4)最長共同子序列(Longest Common Subsequence)
給定兩個英文字母的字串，請找這兩個英文字母字串的最長共同子序列(Longest Common Subsequence)，縮寫為LCS，兩個英文字母字串可以不取其中某些字元，但字母順序不能更換，大小寫英文字母視為不同字母。
(4-1)最長共同子序列—不考慮最佳解路徑
輸入說明
每次輸入兩英文字母字串，求這兩個英文字母字串的最長共同子序列，兩字串長度都不會超過100個字元。
輸出說明
輸出一個整數，表示這兩個英文字母字串的最長共同子序列長度。
輸入範例
comp
zope
輸出範例
2
解題想法
依序考慮兩字串的所有字母，找出最長共同子序列的長度。
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
輸出範例
2
op
解題想法
依序考慮兩字串的所有字母，找出最長共同子序列的長度。
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]可以寫出以下程式。
程式碼
範例練習1 d890-3-禮物分配(gift)
範例練習2 d904: 換零錢
範例練習3 104北市賽 舞會 LCS
範例練習4 100北市賽-3-蛋白質序列比對（Protein）LCS
範例練習5 b006: 95高雄市資訊能力競賽-矩形旋轉
範例練習6 APCS202101 第4題飛黃騰達 排序+LIS
範例練習7 APCS202109 第4題美食博覽會 DP
範例練習8 APCS202010 第3題勇者修煉 DP
範例練習9 APCS201910 第4題刪除邊界 DP 2022.11.9