動態規劃 Dynamic Programming (DP) 101北一女中 資訊選手培訓營 動態規劃 Dynamic Programming (DP) 2012.07.15 Nan

Programming……

Programming @ Math 最佳化問題 Optimization Problem

從切棍子的問題開始

切棍子問題 給你一根棍子，長度為L，你可以任意地把這根棍子切成任意長度的幾段，也可以不切。但不同長度的棍子有不同的價值，要請你算出價值最高的(最佳的)切法。

舉個例子來說 價值如上表，長度為4的棍子有以下8種切法: 把價值高的先切(不切，保留L=4)並不會是最佳解，最佳解是2+2(Value=10) 枚舉所有切的可能性的話，複雜度是指數(就是很大的意思)！

動態規劃法 把大問題切成小問題 (Divide-and-Conquer) 把同樣問題的答案算過後就記下來 決定能算出大問題的小問題是什麼 (最佳子結構) 轉成“遞迴關係” 把同樣問題的答案算過後就記下來

以切棍子來說…… 最佳子結構： 除了最後一段， 在那之前的棍子最大價值(小問題) 最佳子結構： 除了最後一段， 在那之前的棍子最大價值(小問題) 遞迴關係： rod(L) = max 1≤𝑖≤𝐿 (p_i + rod(L – i) ) 𝑖𝑓 𝐿≥1 0 𝑜𝑡ℎ𝑒𝑟𝑤𝑖𝑠𝑒 ; 紀錄： 開一個表格(陣列)紀錄int dp[L];

兩種DP的方式 Bottom-Up (iterative) Top-Down (recursive) 通常直接透過迴圈，表格小的地方開始填，這樣當大的算的時候小的就都填好了。 Top-Down (recursive) 先把表格通通設成像-1之類的值，代表沒填過 之後遞迴呼叫到時，先看看該格是不是-1，不是就回傳該格的值，是就往下遞迴，最後再把值記入該格中。

Bottom-Up解切棍子 int value[L + 1] = {…}; // 各長度的價值 int DP[L + 1]; // 記錄用的表格 int i, j; DP[0] = 0; for ( i = 1 ; i <= L ; i++ ){ DP[i] = 0; for ( j = 1 ; j <= i ; j++ ) if ( DP[i - j] + value[j] > DP[i] ) DP[i] = DP[i – j] + value[j]; }

Top-Down解切棍子 int value[L + 1] = {…}; // 各長度的價值 int DP[L + 1]; // 記錄用的表格 int i, j; void rod_cut(int L){ int i, tmp; if (DP[L] != -1) return DP[L]; DP[L] = 0; for ( i = 1 ; i <= L ; i++ ){ tmp = value[i] + rod_cut(L – i); if ( tmp > DP[L] ) DP[L] = tmp; } int main(){ for ( i = 1 ; i <= L ; i++ ) DP[i] = -1; DP[0] = 0; rod_cut(L);

Bottom-Up解切棍子 大部分時候比較推薦用Bottom-Up！ int value[L + 1] = {…}; // 各長度的價值 int DP[L + 1]; // 記錄用的表格 int i, j; DP[0] = 0; for ( i = 1 ; i <= L ; i++ ){ DP[i] = 0; for ( j = 1 ; j <= i ; j++ ) if ( DP[i - j] + value[j] > DP[i] ) DP[i] = DP[i – j] + value[j]; } 大部分時候比較推薦用Bottom-Up！

Maximum Consecutive Sum, MCS 最大連續元素和 Maximum Consecutive Sum, MCS

問題定義 給你一個序列，值可能有正有負。請你算出從哪裡開始到哪裡結束的元素總和最大。

最直覺的想法 直接枚舉「從i開始到j結束」的所有可能性，再把枚舉的起點到終點加起來，找出最大的那個。 O(n3)

DP的作法 最佳子結構： 在元素i之前的MCS為多少。 遞迴關係： 那從加上我也一定會比較大。 我們要的MCS會是過程中算出來 最大的MCS(i)

標準的Bottom-Up DP int ele[N] = {…}; int MCS[N]; int i, max = 0; MCS[0] = ele[0]; for ( i = 1 ; i < N ; i++ ){ if ( MCS[i – 1] < 0 ) MCS[i] = ele[i]; else MCS[i] = MCS[i – 1] + ele[i]; if ( MCS[i] > max ) max = MCS[i]; } printf(“MCS = %d\n”, max);

稍微修改的Bottom-Up DP int ele[N] = {…}; int sum = 0; int i, max = 0; for ( i = 0 ; i < N ; i++ ){ if ( sum < 0 ) sum = 0; sum += ele[i]; if ( sum > max ) max = sum; } printf(“MCS = %d\n”, max); 因為MCS[x]在x+1之後就不用用到， 所以乾脆從頭到尾只用一個變數sum來放就好。

Longest Increasing Subsequence, LIS 最長遞增子序列 Longest Increasing Subsequence, LIS

問題定義 給你一個序列，你必須要從裡面抓出一些元素，形成一子序列(以在原序列的順序排列)，且此子序列的元素之間具有遞增關係，長度為所有可能的遞增子序列裡最長的。

DP的作法 最佳子結構： 能接在我之前的元素的LIS是多少 遞迴關係 LIS(i) = max 𝑖>𝑗≥1&&𝑒𝑙𝑒 𝑗 <𝑒𝑙𝑒[𝑖] 𝐿𝐼𝑆 𝑖 +1 找出所有在i之前且能接在i前面的元素j，看看誰的LIS+1最大 跟MCS一樣，我們要的LIS會是過程中算出來最大的LIS(i)

Bottom-Up DP int ele[N] = {…}; int LIS[N]; int i, j, max = 0; for ( i = 0 ; i < N ; i++ ) LIS[i] = 1; // 至少有自己 for ( i = 1 ; i < N ; i++ ){ for ( j = 0 ; j < i ; j++ ){ if ( ele[j] < ele[i] && LIS[j] + 1 > LIS[i] ) LIS[i] = LIS[j] + 1; } if ( LIS[i] > max ) max = LIS[i]; printf(“|LIS| = %d\n”, max); 想想看：這個演算法的複雜度是？ 同樣的問題還有更快的作法，但他不能夠“回溯”

LIS的回溯 - 加上一個「我從何而來」的紀錄表格 int ele[N] = {…}; int LIS[N],from[N]; int i, j, max = 0; for ( i = 0 ; i < N ; i++ ){ LIS[i] = 1; // 至少有自己 from[i] = -1; // -1代表從自己來的 } for ( i = 1 ; i < N ; i++ ){ for ( j = 0 ; j < i ; j++ ){ if ( ele[j] < ele[i] && LIS[j] + 1 > LIS[i] ){ LIS[i] = LIS[j + 1]; from[i] = j; if ( LIS[i] > max ) max = LIS[i]; printf(“|LIS| = %d\n”, max);