上目錄：
目錄
題目描述
輸入格式
輸出格式
輸入輸出樣例
說明/提示
一、DP的意義以及線性動規簡介
在一個困難的嵌套決策鏈中，決策出最優解。
二、動態規劃性質淺談
三、子序列問題
（一）一個序列中的最長上升子序列（LIS）
1、n^2做法
下一狀態最優值=最優比較函數（已經記錄的最優值，可以由先前狀態得出的最優值）
2、n^log(n) 做法
（二）兩個序列中的最長公共子序列（LCS）
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?個臺階、2?個臺階或?3?個臺階。現在一共有?N?個臺階，你能幫小楊算算有多少種下樓梯方案嗎？
輸入格式
輸入一行，包含一個整數?N。
輸出格式
輸出一行一個整數表示答案。
輸入輸出樣例
輸入 #1
4
輸出 #1
7
輸入 #2
10
輸出 #2
274
說明/提示
對全部的測試點，保證?1≤N≤60。
周知眾所，連下兩個或三個臺階會讓小楊滾下樓梯，他不會那么做，故輸出1即可。
題目是題目，現實是現實，你不要搶戲！
動態規劃發自內心的一句話。
上面是有名的一個人——騙分神說的話，大家別當真。
一、DP的意義以及線性動規簡介
動態規劃自古以來是DALAO凌虐萌新的分水嶺，但有些OIer認為并沒有這么重要——會打暴力，大不了記憶化。但是其實，動態規劃學得好不好，可以彰顯出一個OIer的基本素養——能否富有邏輯地思考一些問題，以及更重要的——能否將數學、算籌學（決策學）、數據結構合并成一個整體并且將其合理運用。
而我們首先要了解的，便是綜合難度在所有動規題里最為簡單的了。線性動規既是一切動規的基礎，同時也可以廣泛解決生活中的各項問題——比如我們需要決策在相同的時間內做價值盡量大的事情，該如何決策，最優解是什么——這就引出了動態規劃的真正含義：
在一個困難的嵌套決策鏈中，決策出最優解。
二、動態規劃性質淺談
首先，動態規劃和遞推有些相似（尤其是線性動規），但是不同于遞推的是：
遞推求出的是數據，所以只是針對數據進行操作；而動態規劃求出的是最優狀態，所以必然也是針對狀態的操作，而狀態自然可以出現在最優解中，也可以不出現——這便是決策的特性。
其次，由于每個狀態均可以由之前的狀態演變形成，所以動態規劃有可推導性，但同時，動態規劃也有無后效性，即每個當前狀態會且僅會決策出下一狀態，而不直接對未來的所有狀態負責，可以理解為未來與過去無關。
三、子序列問題
（一）一個序列中的最長上升子序列（LIS）
例：由6個數，分別是： 1 7 6 2 3 4，求最長上升子序列。
評析：首先，我們要理解什么叫做最長上升子序列：1、最長上升子序列的元素不一定相鄰 2、最長上升子序列一定是原序列的子集。所以這個例子中的LIS就是：1 2 3 4，共4個
1、n^2做法
首先我們要知道，對于每一個元素來說，最長上升子序列就是其本身。那我們便可以維護一個dp數組，使得dp[i]表示以第i元素為結尾的最長上升子序列長度，那么對于每一個dp[i]而言，初始值即為1.
那么dp數組怎么求呢？我們可以對于每一個i，枚舉在i之前的每一個元素j，然后對于每一個dp[j],如果元素i大于元素j，那么就可以考慮繼承，而最優解的得出則是依靠對于每一個繼承而來的dp值，取max.
for(int i=1;i<=n;i++){dp[i]=1;//初始化 for(int j=1;j<i;j++)//枚舉i之前的每一個j if(data[j]<data[i] && dp[i]<dp[j]+1)//用if判斷是否可以拼湊成上升子序列，//并且判斷當前狀態是否優于之前枚舉//過的所有狀態,如果是，則↓ dp[i]=dp[j]+1;//更新最優狀態 }
最后，因為我們對于dp數組的定義是到i為止的最長上升子序列長度，所以我們最后對于整個序列，只需要輸出dp[n](n為元素個數)即可。
從這個題我們也不難看出，狀態轉移方程可以如此定義：
下一狀態最優值=最優比較函數（已經記錄的最優值，可以由先前狀態得出的最優值）
2、n^log(n) 做法
我們其實不難看出，對于n^2做法而言，其實就是暴力枚舉：將每個狀態都分別比較一遍。但其實有些沒有必要的狀態的枚舉，導致浪費許多時間，當元素個數到了100004?100005以上時，就已經超時了。而此時，我們可以通過另一種動態規劃的方式來降低時間復雜度：
將原來的dp數組的存儲由數值換成該序列中，上升子序列長度為i的上升子序列，的最小末尾數值。
這其實就是一種幾近貪心的思想：我們當前的上升子序列長度如果已經確定，那么如果這種長度的子序列的結尾元素越小，后面的元素就可以更方便地加入到這條我們臆測的、可作為結果、的上升子序列中。
一定要好好看注釋啊！
3、路徑
只要記錄前驅，然后遞歸輸出即可（也可以用棧）
下面貼出完整代碼
#include <iostream>
using namespace std;
const int MAXN = 1000 + 10;
int n, data[MAXN];
int dp[MAXN];
int from[MAXN];
void output(int x)
{if(!x)return;output(from[x]);cout<<data[x]<<" ";//迭代輸出
}
int main()
{cin>>n;for(int i=1;i<=n;i++)cin>>data[i];// DPfor(int i=1;i<=n;i++){dp[i]=1;from[i]=0;for(int j=1;j<i;j++)if(data[j]<data[i] && dp[i]<dp[j]+1){dp[i]=dp[j]+1;from[i]=j;//逐個記錄前驅 }}int ans=dp[1], pos=1;for(int i=1;i<=n;i++)if(ans<dp[i]){ans=dp[i];pos=i;//由于需要遞歸輸出//所以要記錄最長上升子序列的最后一//個元素，來不斷回溯出路徑來 }cout<<ans<<endl;output(pos);return 0;
}
（二）兩個序列中的最長公共子序列（LCS）
1、譬如給定2個序列：
1 2 3 4 53 2 1 4 5
試求出最長的公共子序列。
顯然長度是3，包含3??4??5?三個元素（不唯一）
解析：我們可以用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]
那么代碼:
#include<iostream>
using namespace std;
int dp[1001][1001],a1[2001],a2[2001],n,m;
int main()
{//dp[i][j]表示兩個串從頭開始，直到第一個串的第i位 //和第二個串的第j位最多有多少個公共子元素 cin>>n>>m;for(int i=1;i<=n;i++)scanf("%d",&a1[i]);for(int i=1;i<=m;i++)scanf("%d",&a2[i]);for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){dp[i][j]=max(dp[i-1][j],dp[i][j-1]);if(a1[i]==a2[j])dp[i][j]=max(dp[i][j],dp[i-1][j-1]+1);//因為更新，所以++； }cout<<dp[n][m];
}
2、而對于洛谷P1439而言，不僅是卡上面的樸素算法，也考察到了全排列的性質：
對于這個題而言，樸素算法是n^2的，會被10^5卡死，所以我們可以考慮nlogn的做法：
因為兩個序列都是1?n的全排列，那么兩個序列元素互異且相同，也就是說只是位置不同罷了，那么我們通過一個map數組將A序列的數字在B序列中的位置表示出來——
因為最長公共子序列是按位向后比對的，所以a序列每個元素在b序列中的位置如果遞增，就說明b中的這個數在a中的這個數整體位置偏后，可以考慮納入LCS——那么就可以轉變成nlogn求用來記錄新的位置的map數組中的**LIS**。
最后貼n^log(n)代碼：
#include<iostream>
#include<cstdio>
using namespace std;
int a[100001],b[100001],map[100001],f[100001];
int main()
{int n;cin>>n;for(int i=1;i<=n;i++){scanf("%d",&a[i]);map[a[i]]=i;}for(int i=1;i<=n;i++){scanf("%d",&b[i]);f[i]=0x7fffffff;}int len=0;f[0]=0;for(int i=1;i<=n;i++){int l=0,r=len,mid;if(map[b[i]]>f[len])f[++len]=map[b[i]];else {while(l<r){ mid=(l+r)/2;if(f[mid]>map[b[i]])r=mid;else l=mid+1; }f[l]=min(map[b[i]],f[l]);}}cout<<len;return 0
}那么，這個題怎么解？
顯然，設dp[i]為下到第i級臺階時的走法數，則有dp[i]=dp[i-1]+dp[i-2]+dp[i-3];
dp[0]=1;不走也是一種走法
dp[1]=1;
dp[2]=2;
dp[3]=4;
好啦，你過了六級的第一關！不過是不是有跳關通道？我不知道啊。
)
)
