一、說明

動態規劃似乎針對問題很多，五花八門，似乎每一個問題都有一套具體算法。其實不是的，動態規劃只有兩類：1）針對圖的路徑問題 2）針對一個序列的問題。本篇講動態規劃針對序列的算法范例。

二、動態規劃解決的問題

1 動態規劃針對什么問題？
1）從0到N是個規模膨脹的遞歸問題。
2）如果$f(N?1)$有解，那么可以推導出$f(N)$的解。

2 動態規劃可以解決的問題特點：
1）按照規模遞增的關系，凡是問題$f(N)$的解依賴于$f(N?1)$的解。
2）算法從$f(0)$出發，能推導出$f(1)$的解，然后正向求解。

3 兩類動態規劃的問題
動態規劃似乎針對問題很多，五花八門，每一個問題都有一套具體算法。其實不是的，動態規劃只有兩類：1）針對圖的路徑問題 2）針對一個序列的問題。
本篇講動態規劃針對序列的算法范例。

三、動態規劃解決最大上升子序列問題

3.1 問題描述

問題提出：對于序列$a_1,a_2,...a_n$找到一個最長的遞增序列$a_{i_1},a_{i_2}...a_{i_k}$,其中，$i_1<i_2,...<i_n$且，$a_{i_1}<a_{i_2}...<a_{i_k}$
示例：

對于序列【 5， 2， 8 ，6， 3， 6， 9， 5 】的最長上升子序列長度：

答案是：
【2，3，6，9】

3.2 算法描述

法則：
LIS[n]=1+max{LIS[n?1]∣k<n,A[k]<A[n]}LIS[n]=1+max\{LIS[n-1]|k<n,A[k]<A[n]\}LIS[n]=1+max{LIS[n?1]∣k<n,A[k]<A[n]}
下面對一個序列進行逐步解釋：
求下列序列的最大上升子序列：
【 5， 2， 8 ，6， 3， 6， 9， 5 】

解：先命名兩個序列iem和lenght，分別存儲當前值和對應長度。
建立iem序列：【 5， 2， 8 ，6， 3， 6， 9， 5 】
lenght序列：
【 1， 1， 1 ，1， 1， 1， 1， 1 】

• 預先給出每個元素初始長度為“1”

開始掃描：
step1：對序列ltem【0】元素進行掃描，由于沒有前序，所以【0】的長度依然是1：length【0】=1

step2：對序列ltem【1】元素進行掃描，由于前序是5（大于本地的2），所以【1】的長度依然是1：length【1】=1

step3：對序列item【2】元素進行掃描，由于前序是5和2，小于本地的8，所以len_max（length【0】，length【1】）=1，所以，length【2】=len_max+length【2】=2

step4：對序列item【3】元素進行掃描，本地的6，小于本地6的前序是5和2，所以len_max（length【0】，length【1】）=1，所以，length【3】=len_max+length【3】=2

step5：對序列item【4】元素進行掃描，本位值3，小于本地3的前序是2，所以len_max（length【2】）=1，所以，length【4】=len_max+length【4】=2

step6：對序列item【5】元素進行掃描，本位值6，小于本地6的前序是【5，2.3】，所以len_max（length【0】，length【1】，length【4】）=2，所以，length【5】=len_max+length【5】=3

step7：對序列item【6】元素進行掃描，本位值9，小于本地6的前序是【5，2，8，6，3，6】，所以len_max（length【0】，length【1】，length【2】…）=3，所以，length【6】=len_max+length【6】=4

step8：對序列item【7】元素進行掃描，本位值5，小于本地5的前序是【2，3】，所以len_max（length【2】，length【3】）=2，所以，length【7】=len_max+length【7】=3

3.3 算法代碼

用python給出整個代碼：

def lis(A):L =[1]*len(A)for i in range(1,len(L)):subproblem = [ L[k] for k in range(i) if A[k]<A[i]]L[i] = 1 +max(subproblem,default=0)return max(L,default=0)