動態規劃（DP）-有解無憂

動態規劃（ Dongtai Planning Dynamic Programming，簡稱DP）

多階段決策程序的最優化問題

在現實生活中，有一類活動的程序，由于它的特殊性，可將程序分成若干個互相聯系的階段，在它的每一階段都需要作出決策，從而使整個程序達到最好的活動效果，當然，各個階段決策的選取不是任意確定的，它依賴于當前面臨的狀態，又影響以后的發展，當各個階段決策確定后，就組成一個決策序列，因而也就確定了整個程序的一潭訓動路線，這種把一個問題看作是一個前后關聯具有鏈狀結構的多階段程序就稱為多階段決策程序，這種問題就稱為多階段決策問題，如下圖所示：

多階段決策程序，是指這樣的一類特殊的活動程序，問題可以按時間順序分解成若干相互聯系的階段，在每一個階段都要做出決策，全部程序的決策是一個決策序列，

基本概念

動態規劃是解決 “多階段決策問題”的一種高效演算法，

動態規劃是通過合理組合子問題的解從而解決整個問題解的程序，

動態規劃是通過拆分問題，定義問題狀態和狀態之間的關系，使得問題能夠以遞推（或者說分治）的方式去解決，

即把一個問題轉化為若干個形式相同，但規模更小的子問題，從而遞回解決整個問題，

其中的子問題并不是獨立的，這些子問題又包含有公共的子子問題......

動態規劃演算法對每個子問題只求一次，并將其結果保存在一張表中(陣列)，以后再用到時直接從表中拿過來使用，避免重復計算相同的子問題，
“不做無用功”的求解模式，大大提高了程式的效率，

如何拆分問題，才是動態規劃的核心，
而拆分問題，靠的就是狀態的定義和狀態轉移方程的定義，

真正含義

在一個困難的嵌套決策鏈中，決策出最優解，

本質

對問題狀態的定義和狀態轉移方程的定義，

狀態轉移的實質

決策

動態規劃的基本概念和基本模型構成

階段、狀態、決策、策略、狀態轉移方程

階段和階段變數
用動態規劃求解一個問題時，需要將所給問題的全程序恰當地分成若干個相互聯系的階段，以便按一定的次序去求解，

程序不同，階段數就可能不同，

描述階段的變數稱為階段變數，在多數情況下，階段變數是離散的，用k表示，
階段的劃分一般是根據時間和空間的自然特征來劃分，

階段的劃分要便于把問題轉化成多階段決策問題，

狀態和狀態變數
某一階段的出發位置稱為狀態，通常一個階段有多個狀態，
一般地，狀態可以用一個或一組數（變數）來描述，用來描述狀態的變數稱為狀態變數，

決策、決策變數和決策允許集合
一個階段的狀態給定以后，從該階段的每一個狀態出發，通過一次選擇性的行動轉移至下一階段的相應狀態稱為決策，

或者說在對問題的處理中作出的每種選擇性的行動就是決策，

一個實際問題可能要有多次決策和多個決策點，在每一個階段的每一個狀態中都需要有一次決策，

決策可以用變數來描述，這種描述決策的變數稱為決策變數，
在實際問題中，決策變數的取值往往限制在某一個范圍之內，此范圍稱為允許決策集合，

策略和最優策略

全程序中各階段決策變數所組成的有序總體稱為策略，
所有階段的決策有序組合構成一個策略，

在實際問題中，最優效果的策略叫最優策略，

狀態轉移方程
前一階段的終點就是后一階段的起點，對前一階段的狀態作出某種決策，產生后一階段的狀態，這種關系描述了由k階段到k+1階段狀態的演變規律，稱為狀態轉移方程，

條件

拓撲圖（DAG，有向無環圖）（可拓撲排序）

最優子結構

即，子問題的最優解是整個問題的最優解的一部分，

無后效性

性質

布爾性

動態規劃和遞推有些相似（尤其是線性動規），但是不同于遞推的是：

遞推求出的是資料，所以只是針對資料進行操作；而動態規劃求出的是最優狀態，所以必然也是針對狀態的操作，而狀態自然可以出現在最優解中，也可以不出現——這便是決策的特性（布爾性），

批判性繼承思想

狀態轉移方程可以如此定義：

下一狀態最優值=最優比較函式（已經記錄的最優值，可以由先前狀態得出的最優值）

——即動態規劃具有判斷性繼承思想

可推導性

由于每個狀態均可以由之前的狀態演變形成，所以動態規劃有可推導性，

最優化原理
整個程序的最優策略具有：無論過去的狀態和決策如何，對前面的決策所形成的狀態而言，余下的決策必須構成最優策略的性質，
即，子問題的區域最優將導致整個問題的全域最優，
即，問題具有最優子結構的性質，
也就是說一個問題的最優解只取決于其子問題的最優解，而非最優解對問題的求解沒有影響，
無后效性原則
某階段的狀態一旦確定，則此后程序的演變不再受此前各狀態及決策的影響，

即每個當前狀態會且僅會決策出下一狀態，而不直接對未來的所有狀態負責，

也就是說，“未來與過去無關”，當前的狀態是此前歷史的一個完整的總結，此后的歷史只能通過當前的狀態去影響程序未來的演變，

可以淺顯地理解為：

Future never has to do with past time ,but present does.

現在決定未來，未來與過去無關，

若直接縮小規模而劃分出的子問題不滿足最優子結構

引入更多用于區分不同子問題的“狀態”，

對于不能劃分階段的問題，不能運用動態規劃來解；
對于能劃分階段，但不符合最優化原理的，也不能用動態規劃來解；
既能劃分階段，又符合最優化原理的，但不具備無后效性原則，不能用動態規劃來解，

方式

正推：
從初始狀態開始，通過對中間階段的決策的選擇，達到結束狀態，我們也稱之為遞推，
倒推：
從結束狀態開始，通過對中間階段的決策的選擇，達到初始狀態，我們可以稱之為記憶化搜索，

把大象裝進冰箱 寫出一個DP需要幾步？

劃分階段
確定狀態和狀態變數

除了“問題的規模”這一直接的狀態，還應考慮一些附加的，用來滿足“最優子結構”這一性質的額外狀態，
確定決策并寫出狀態轉移方程

根據狀態的實際意義去轉移，一般有兩種考慮方式：“如何分解”和“如何合并”，根據實際選擇，
尋找邊界條件

分析復雜度

時間復雜度=狀態總數x單次轉移復雜度
編程實作程式（正推或倒推）

注意各類邊界，注意資料型別（爆int？double精度？）

優化

削減狀態

優化轉移

應用

計數類問題（統計方案總數）

最優決策類問題（最大值或最小值）

記憶化搜索

記憶化搜索=搜索的形式+動態規劃的思想，

記憶化搜索的思想是,在搜索程序中，會有很多重復計算,如果我們能記錄一些狀態的答案，就可以減少重復搜索量

近似于暴力

線性DP

綜合難度在所有動規題里最為簡單，

線性動規既是一切動規的基礎，同時也可以廣泛解決生活中的各項問題——比如在我們所在的三維世界里，四維的時間就是不可逆式線性，

線性動態規劃是在線性結構上進行狀態轉移，這類問題不像背包問題、區間DP等有固定的模板，

線性動態規劃的目標函式為特定變數的線性函式，約束是這些變數的線性不等式或等式，目的是求目標函式的最大值或最小值，

例題

子序列問題

LIS (Longest Increasing Subsequence，最長上升子序列)

最長上升子序列的元素不一定相鄰

最長上升子序列一定是原序列的子集，

給定n個元素的數列，求最長的上升子序列長度，
這類動態規劃問題的狀態一般是一維的f[i]，第i個元素的最優值只與前i-1個元素的最優值（正推）或第i+1個元素之后的最優值（倒推）有關，

n^2做法

首先，對于每一個元素來說，其最長上升子序列就是其本身，那我們便可以維護一個dp陣列，使得dp[i]表示以第i元素為結尾的最長上升子序列長度，那么對于每一個dp[i]而言，初始值即為1；

那么dp陣列怎么求呢？我們可以對于每一個i，列舉在i之前的每一個元素j，然后對于每一個dp[j],如果元素i大于元素j，那么就可以考慮繼承，而最優解的得出則是依靠對于每一個繼承而來的dp值取max，

 1 for(int i=1;i<=n;i++)
 2     {
 3         dp[i]=1;//初始化 
 4         for(int j=1;j<i;j++)//列舉i之前的每一個j 
 5         if(data[j]<data[i] && dp[i]<dp[j]+1)
 6         /*用if判斷是否可以拼湊成上升子序列，
 7           并且判斷當前狀態是否優于之前列舉
 8           過的所有狀態,如果是，則↓*/
 9         dp[i]=dp[j]+1;//更新最優狀態 
10         
11     }

最后，因為我們對于dp陣列的定義是到i為止的最長上升子序列長度，所以我們最后對于整個序列，只需要輸出dp[n](n為元素個數)即可，

nlogn 做法

我們其實不難看出，對于n^2做法而言，其實就是暴力列舉：將每個狀態都分別比較一遍，但其實有些沒有必要的狀態的列舉，導致浪費許多時間，當元素個數到了10^4-10^5以上時，就已經超時了，而此時，我們可以通過另一種動態規劃的方式來降低時間復雜度：

將原來的dp陣列的存盤由數值換成該序列中，上升子序列長度為i的上升子序列的最小末尾數值，

這其實就是一種幾近貪心的思想：我們當前的上升子序列長度如果已經確定，那么如果這種長度的子序列的結尾元素越小，后面的元素就可以更方便地加入到這條我們臆測的、可作為結果的上升子序列中，

 1 int n;
 2     cin>>n;
 3     for(int i=1;i<=n;i++)
 4     {
 5         cin>>a[i];
 6         f[i]=0x7fffffff;
 7         //初始值要設為INF
 8         /*原因很簡單，每遇到一個新的元素時，就跟已經記錄的f陣列當前所記錄的最長
 9           上升子序列的末尾元素相比較：如果小于此元素，那么就不斷向前找，直到找到
10           一個剛好比它大的元素，替換；反之如果大于，么填到末尾元素的下一個q，INF
11           是為了方便向后替換*/ 
12     }
13     f[1]=a[1];
14     int len=1;//通過記錄f陣列的有效位數，求得個數 
15     /*因為上文中所提到我們有可能要不斷向前尋找，
16     所以可以采用二分查找的策略，這便是將時間復雜
17     度降成nlogn級別的關鍵因素，*/ 
18     for(int i=2;i<=n;i++)
19     {
20         int l=0,r=len,mid;
21         if(a[i]>f[len])f[++len]=a[i];
22         //如果剛好大于末尾，暫時向后順次填充 
23         else 
24         {
25         while(l<r)
26         {    
27             mid=(l+r)/2;
28             if(f[mid]>a[i])r=mid;
29     /*如果仍然小于之前所記錄的最小末尾，那么不斷
30       向前尋找(因為是最長上升子序列，所以f陣列必
31       然滿足單調)*/
32             else l=mid+1; 
33         }
34         f[l]=min(a[i],f[l]);//更新最小末尾 
35          }
36     }
37     cout<<len;

Another Situation

但是事實上，nlogn做法偷了個懶，沒有記錄以每一個元素結尾的最長上升子序列長度，那么我們對于n^2的統計方案數，有很好想的如下代碼（再對第一次的dp陣列dp一次）：

1 for(i = 1; i <= N; i ++){
2     if(dp[i] == 1) f[i] = 1 ;
3     for(j = 1; j <= N: j ++)
4         if(base[i] > base[j] && dp[j] == dp[i] - 1) f[i] += f[j] ;
5         else if(base[i] == base[j] && dp[j] == dp[i]) f[i] = 0 ;
6     if(f[i] == ans) res ++ ;
7     }

nlogn雖然好像也可以做，但是想的話會比較麻煩，在這里就暫時不討論了QwQ，

但這件事的目的是為了論證一個觀點：

時間復雜度越高的演算法越全能，

輸出路徑

只要記錄前驅，然后遞回輸出即可（也可以用堆疊的），

n^2的完整代碼

 1 #include <iostream>
 2 using namespace std;
 3 const int MAXN = 1000 + 10;
 4 int n, data[MAXN];
 5 int dp[MAXN]; 
 6 int from[MAXN]; 
 7 void output(int x)
 8 {
 9     if(!x)return;
10     output(from[x]);
11     cout<<data[x]<<" ";
12     //迭代輸出 
13 }
14 int main()
15 {
16     cin>>n;
17     for(int i=1;i<=n;i++)cin>>data[i];
18     
19     // DP
20     for(int i=1;i<=n;i++)
21     {
22         dp[i]=1;
23         from[i]=0;
24         for(int j=1;j<i;j++)
25         if(data[j]<data[i] && dp[i]<dp[j]+1)
26         {
27             dp[i]=dp[j]+1;
28             from[i]=j;//逐個記錄前驅 
29         }
30     }
31     
32     int ans=dp[1], pos=1;
33     for(int i=1;i<=n;i++)
34         if(ans<dp[i])
35         {
36             ans=dp[i];
37             pos=i;/*由于需要遞回輸出
38     　 所以要記錄最長上升子序列的最后一
39       個元素，來不斷回溯出路徑來*/
40         }
41     cout<<ans<<endl;
42     output(pos);
43     
44     return 0;
45 }

補：
最長上升子序列長度 <
最長不下降子序列長度 <=
最長下降子序列長度 >
最長不上升子序列長度 >=

最長公共子序列（LCS）

我們可以用dp[i][j]來表示第一個串的前i位，第二個串的前j位的LCS的長度，那么我們是很容易想到狀態轉移方程的：

如果當前的A1[i]和A2[j]相同（即是有新的公共元素）那么

dp[ i ] [ j ] = max(dp[ i ] [ j ], dp[ i-1 ] [ j-1 ] + 1)；

如果不相同，即無法更新公共元素，考慮繼承：

dp[ i ] [ j ] = max(dp[ i-1 ][ j ] , dp[ i ][ j-1 ]）；

 1 #include<iostream>
 2 using namespace std;
 3 int dp[1001][1001],a1[2001],a2[2001],n,m;
 4 int main()
 5 {
 6    //dp[i][j]表示兩個串從頭開始，直到第一個串的第i位 
 7    //和第二個串的第j位最多有多少個公共子元素 
 8    cin>>n>>m;
 9    for(int i=1;i<=n;i++)scanf("%d",&a1[i]);
10    for(int i=1;i<=m;i++)scanf("%d",&a2[i]);
11    for(int i=1;i<=n;i++)
12     for(int j=1;j<=m;j++)
13      {
14          dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
15          if(a1[i]==a2[j])
16          dp[i][j]=max(dp[i][j],dp[i-1][j-1]+1);
17          //因為更新，所以++； 
18      }
19    cout<<dp[n][m];
20 }

對于洛谷P1439而言，不僅是卡上面的樸素演算法，也考察到了全排列的性質：

對于這個題而言，樸素演算法是n^2的，會被10^5卡死，所以我們可以考慮nlogn的做法：

因為兩個序列都是1~n的全排列，那么兩個序列元素互異且相同，也就是說只是位置不同罷了，那么我們通過一個map陣列將A序列的數字在B序列中的位置表示出來——

因為最長公共子序列是按位向后比對的，所以a序列每個元素在b序列中的位置如果遞增，就說明b中的這個數在a中的這個數整體位置偏后，可以考慮納入LCS——那么就可以轉變成nlogn，即求用來記錄新的位置的map陣列中的LIS，

 1 #include<iostream>
 2 #include<cstdio>
 3 using namespace std;
 4 int a[100001],b[100001],map[100001],f[100001];
 5 int main()
 6 {
 7     int n;
 8     cin>>n;
 9     for(int i=1;i<=n;i++){scanf("%d",&a[i]);map[a[i]]=i;}
10     for(int i=1;i<=n;i++){scanf("%d",&b[i]);f[i]=0x7fffffff;}
11     int len=0;
12     f[0]=0;
13     for(int i=1;i<=n;i++)
14     {
15         int l=0,r=len,mid;
16         if(map[b[i]]>f[len])f[++len]=map[b[i]];
17         else 
18         {
19         while(l<r)
20         {    
21             mid=(l+r)/2;
22             if(f[mid]>map[b[i]])r=mid;
23             else l=mid+1; 
24         }
25         f[l]=min(map[b[i]],f[l]);
26          }
27     }
28     cout<<len;
29     return 0
30 }