顾名思义，线性DP就是在一条线上进行DP，这里举一些典型的例子。
LIS问题（最长上升子序列问题）
题目
给定一个长度为N的序列A，求最长的数值单调递增的子序列的长度。
上升子序列B可表示为B={Ak1,Ak2,···,Akp}，其中k1<k2<···<kp。
解析
状态：F[i]表示以A[i]为结尾的最长上升子序列的长度，边界为f[0]=0。
状态转移方程：F[i]=max{F[j]+1}(0≤j<i,A[j]<A[i])。
答案显然为max{F[i]}(1≤i≤N)。
事实上，无论是上升、下降还是不上升等等此类问题，代码都是相似的，唯一的区别只是判断的符号更改罢了。
Code
#include <iostream> using namespace std; int n,a[100],f[100],maxn; int main() { f[0]=0; cin>>n; for(int i=1;i<=n;i++) { cin>>a[i]; for(int j=1;j<n;j++) if(a[j]<a[i]) f[i]=max(f[i],f[j]+1); maxn=max(maxn,f[i]); } cout<<maxn; return 0; }
LCS问题（最长公共子序列）
题目
给定两个长度分别为N、M的字符串A和B，求最长的既是A的子序列又是B的子序列的字符串的长度。
解析
状态：F[i][j]表示A的前i个字符与B的前j个字符中的最长公共子序列，边界为F[i][0]=F[0][j]=0。
状态转移方程：F[i][j]=max{F[i-1][j],F[i][j-1],F[i-1][j-1]+1(if A[i]=B[j])}。
答案为F[N][M]。
Code
#include <iostream> using namespace std; int n,m,f[100][100]; char a[100],b[100]; int main() { cin>>n>>m; for(int i=1;i<=n;i++) { cin>>a[i]; f[i][0]=0; } for(int i=1;i<=m;i++) { cin>>b[i]; f[0][i]=0; } for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) { f[i][j]=max(f[i-1][j],f[i][j-1]); if(a[i]==b[j]) f[i][j]=max(f[i][j],f[i-1][j-1]+1); } cout<<f[n][m]; return 0; }
数字三角形
题目
给定一个N行的三角矩阵A，其中第i行有i列，从左上角出发，每次可以向下方或向右下方走一步，最终到达底部。
求把经过的所有位置上的数加起来，和最大是多少。
解析
状态：F[i][j]表示走到第i行第j列，和最大是多少，边界为F[1][1]=A[1][1]。
状态转移方程：F[i][j]=A[i][j]+max{F[i-1][j],F[i-1][j-1](if j>1)}。
答案为max{F[N][j]}(1≤j≤N)。
Code
#include <iostream> using namespace std; int n,a[100][100],f[100][100],maxn; int main() { cin>>n; for(int i=1;i<=n;i++) for(int j=1;j<=i;j++) cin>>a[i][j]; f[1][1]=a[1][1]; for(int i=1;i<=n;i++) for(int j=1;j<=i;j++) { f[i][j]=a[i][j]+f[i-1][j]; if(j>1) f[i][j]=max(f[i][j],a[i][j]+f[i-1][j-1]); } for(int i=1;i<=n;i++) maxn=max(maxn,f[n][i]); cout<<maxn; return 0; }
例题一：合唱队形
题目
【题目描述】
N位同学站成一排，音乐老师要请其中的(N-K)位同学出列，使得剩下的K位同学排成合唱队形。
合唱队形是指这样的一种队形：设K位同学从左到右依次编号为1,2,…,K，他们的身高分别为T1?,T2?,…,TK?， 则他们的身高满足T1?<...<Ti?>Ti+1?>…>TK?(1≤i≤K)。
你的任务是，已知所有N位同学的身高，计算最少需要几位同学出列，可以使得剩下的同学排成合唱队形。
【输入格式】
共二行。
第一行是一个整数N(2≤N≤100)，表示同学的总数。
第二行有n个整数，用空格分隔，第i个整数Ti?(130≤Ti?≤230)是第i位同学的身高(厘米)。
【输出格式】
一个整数，最少需要几位同学出列。
【输入样例】
8 186 186 150 200 160 130 197 220
【输出样例】
4
【数据规模】
对于50％的数据，保证有n≤20；
对于全部的数据，保证有n≤100。
解析
最少出列，就是最多留下。
分析一下队形，其实质便是先上升再下降，不难联想到最长上升子序列与最长下降子序列。
定义状态F[i][0/1]，F[i][0]表示以第i个人为结尾的最长上升子序列，F[i][1]表示以第i个人为结尾的最长合唱队形，F数组初值都为1,。
所以前i个人的最长合唱队形为max(F[i][0],F[i][1])。
状态转移方程：
F[i][0]=max(F[i][0],F[j][0]+1(if T[i]>T[j]))；(T[i]如题所述，j<i)
F[i][1]=max(F[i][1],a[j][0],a[j][1]+1(if T[i]<T[j])；
最后的答案为n-max(F[i][0],F[i][1])。
Code
#include <algorithm> #include <iostream> #include <cstring> #include <string> #include <cstdio> #include <cmath> using namespace std; int n,t[10