動態規劃是一種通過把原問題分解為相對簡單的子問題的方式求解複雜問題的方法。 -----OI Wiki

例.1-最大子段和

分析

DP四步

⑴定義狀態

定義\(dp_i\)表示以\(i\)結尾的最大子段和

⑵分析答案

答案即\({\max}^{i\in[1,n]}_{dp_i}\)

⑶分析方程

對於每個\(i\)：

1. 可以與\([1,i-1]\)的最大子段和拼接，組成新的子段和\((dp_{i-1}+a_i)\)
2. 可以自己單獨成一個子段和\(a_i\)

求\(\max\)

⑷邊界條件

即\(dp_1\)為\(a_1\)

代碼實現

遞歸寫法

定義\(f(i)\)為以\(i\)結尾的最大子段和
則遞歸分析即可

int f(int x){
	if(x==1){//邊界條件
		return a[1];
	}
	return max(f(x-1)+a[x],a[x]);//求最大值
、}

這樣時間很慢，原因是存在許多已經算過的節點被重複計算
所以用一個\(val\)記錄計算過的節點信息

for(int i=1;i<=n;i++){
	dp[i]=inf;
}
int f(int x){
	if(dp[x]!=inf){
		return dp[x];//已經記錄過的節點信息
	}
	if(x==1){//邊界條件
		return a[1];
	}
	dp[x]=max(f(x-1)+a[x],a[x]);//求最大值
	return dp[x];
}

上述優化方法即記憶化搜索，是一種基本DP方法

記憶化搜索是一種通過記錄已經遍歷過的狀態的信息，從而避免對同一狀態重複遍歷的搜索實現方式。 ------OI Wiki

轉成遞推形式就成了基本的線性DP

dp[1]=a[1];
for(int i=2;i<=n;i++){
	dp[i]=max(dp[i-1]+a[i],a[i]);
	maxi=max(maxi,dp[i]);
}

例.2-最長上升子序列(LIS)

分析

DP四步

⑴定義狀態

定義\(dp_i\)表示以\(i\)結尾的最長上升子序列長度

⑵分析答案

答案即\({\max}^{i\in[1,n]}_{dp_i}\)

⑶分析方程

對於每個\(i\)，有若干\(j<i\)且\(a_j<a_i\)：

1. 可以與每一個\(j\)的最長上升子序列拼接，組成新的子序列長度\((dp_{j}+1)\)
2. 可以自己單獨成一個子段和\(1\)

求\(\max\)

⑷邊界條件

即\(dp_i\)為\(1\)，因為每個\(dp\)值至少為\(1\)

代碼實現

使用遞推，枚舉\(i\),並且枚舉\(j(j<i)\)

for(int i=1;i<=n;i++){
	dp[i]=1;
	for(int j=1;j<i;j++){
		if(a[j]<a[i]){
			dp[i]=max(dp[j]+1,dp[i]);
		}
	}
	maxi=max(maxi,dp[i]);
}

重點題-導彈攔截

50分做法

第一小問即求最長不上升子序列長度
第二問可以用Dilworth 定理解決
把序列分成不上升子序列的最少個數，等於序列的最長上升子序列長度。把序列分成不降子序列的最少個數，等於序列的最長下降子序列長度。
所以第二問等價於求最長上升子序列長度

100分做法

使用貪心優化如果，如果一個位置可以有\(2,3\)兩個數選一個數，我們一定會選\(2\)，因為選2後面就有更多的機會拼接。
定義一個\(c\)數組存貯已經選了的數
只要每次二分查找第一個能夠等價替換的數，就能將其替換，在過程中記錄DP即可。

具體代碼

補充

DP的要素：

1. 數據範圍較小
2. 可以拆解為多個子問題