图等晚上画完再发……
简单的动态规划问题主要包括两个部分，第一个线性动态规划等等，第二个就是简单的动态规划问题（见另一篇博客）。
这篇博客主要讲线性动态规划。
最最经典的问题就是求最长不下降子序列，例如一本通P270-P282页内容，例题全部都是最长不下降子序列的变种。
最长不下降子序列的基本思路是：
处理第某位元素，查找它可以连接到的长度最大的最长不下降序列，也就是搜索它之前的所有元素，找到能够跟它连接的元素（也就是比它小的），然后在找到的元素里找出连接有最长的序列的那一个，然后连接。搜索完毕整个序列后，整个序列里长度最大的值就是所求的最长不下降序列的长度。
OK，上例题 （都是标准的求最长不下降序列问题，模板可直接过）：
（1） 洛谷【P1020】导弹拦截 ：
#include<iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int main(){
//freopen("1.txt","r",stdin);
int j,k,x;
int a[10000],b[10000],h[10000];
int i=1,n=0,m=0;
while (cin>>a[i]) {
int maxx=0;
for(j=1;j<=i-1;j++){
if(a[j]>=a[i]) if(b[j]>maxx) maxx = b[j];}
b[i] = maxx+1;
if(b[i]>m) m=b[i];
x=0;
for(k=1;k<=n;k++){
if(h[k]>=a[i]){
if(x==0) x=k;
else if(h[k]<h[x]) x=k;
}
}
if(x==0){n++;x=n;}
h[x] = a[i];i++;
}
cout<<m<<endl<<n<<endl;
}
（2）洛谷 【P1091】合唱队形 ：
#include<iostream>
#include<cstdio>
using namespace std;
int a[1000],b[1000],c[1000];
int main(){
int n,maxx;
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
}
for(int i =1;i<=n;i++){
b[i] = 1;
for(int j=1;j<=i-1;j++){
if((a[i]>a[j])&&b[j]+1>b[i]){
b[i]=b[j]+1;
}
}
}
for(int i=n;i>=1;i--){
c[i]=1;
for(int j=i+1;j<=n;j++){
if((a[j]<a[i])&&(c[j]+1>c[i])) c[i] = c[j]+1;
}
}
maxx=0;
for(int i=1;i<=n;i++){
if(b[i]+c[i]>maxx){
maxx=b[i]+c[i];
}
}
cout<<n-maxx+1;
}