1. 案例提出
给定一个由n个正整数组成的序列，从该序列中删除若干个整数，使剩下的整数组成非降子序列，求最长的非降子序列。
例如，由12个正整数组成的序列为：
48，16，45，47，52，46，36，28，46，69，14，42
请在序列中删除若干项，使剩下的项为非降（即后面的项不小于后面的项）序列，剩下的非降序列最长为多少项？
2．递推实现动态规划设计
设序列的各项为a[1],a[2],…,a[n]（可随机产生，也可从键盘依次输入），对每一个整数操作为一个阶段，共为n个阶段。
（1）建立递推关系
设置b数组，b[i]表示序列的第i个数（保留第i个数）到第n个数中的最长非降子序列的长度，i=1,2,…,n。对所有的j>i，比较当a[j]≥a[i]时的b[j]的最大值，显然b[i]为这一最大值加1，表示加上a[i]本身这一项。
因而有递推关系：
b[i]=max(b[j])+1 (a[j]≥a[i],1≤i<j≤n)
边界条件：b[n]=1
（2）逆推计算最优值
b[n]=1;
for(i=n−1;i>=1;i−−)
{max=0;for(j=i+1;j<=n;j++)
if(a[i]<=a[j]&& b[j]>max)
max=b[j];
b[i]=max+1; // 逆推得b[i]
}
逆推依次求得b[n−1],…,b[1]，比较这n−1个值得其中的最大值lmax，即为所求的最长非降子序列的长度即最优值。
（3）构造最优解
从序列的第1项开始，依次输出b[i]分别等于lmax,lmax−1,…,1的项a[i]，这就是所求的一个最长非降子序列。
3. 递归实现动态规划设计
（1）建立递归关系
设q(i)表示序列的第i个数（保留第i个数）到第n个数中的最长非降子序列的长度，i=1,2,…,n。对所有的j>i，比较当a[j]≥a[i]时的q(j)的最大值，显然q(i)为这一最大值加1，表示加上a[i]本身这一项。
因而有递归关系：
q(i)=max(q(j))+1 (a[j]≥a[i],1≤i<j≤n)
递归出口：q(n)=1
（2）递归函数设计
int q(int i)
{int j,f,max;
if(i==n)f=1;
else
{ max=0;
for(j=i+1;j<=n;j++)
if(a[i]<=a[j]&& q(j)>max)
max=q(j);
f=max+1;
}
returnf;
}
(3) 在主函数中依次调用q(n−1),…,q(1)，比较这n−1个值得其中的最大值lmax，即为所求的最长非降子序列的长度即最优值。
（4）构造最优解
从序列的第1项开始，依次输出q(i)分别等于lmax,lmax−1,…,1所那就的项a[i]，这就是所求的一个最长非降子序列。
（5）递归实现动态规划程序设计
// 递归实现动态规划
package basic_practice;import java.util.Scanner;public class anlian_bfs {static int a[]=new int[20];//默认值为0static int n;static int q(int i){//第i个数字到第n个数字的最长非降数字个数int j,f,max;if(i==n)f=1;//递归出口，如果是第n个数，则为1else {max=0;for(j=i+1;j<n;j++){if(a[j]>a[i]&&q(j)>max){//因为a[i]比a[j]小，所以a[i]就可以加入a[j]到a[n]构成的非降序列，长度加一max=q(j);}}f=max+1;//长度加一}return f;}public static void main(String[] args) {Scanner in=new Scanner(System.in);n=in.nextInt();for(int i=0;i<n;i++)a[i]=in.nextInt();int lmax=0;for(int i=n-1;i>=1;i--) if(q(i)>lmax) lmax=q(i); //逐个比较求最大System.out.println(lmax);//System.out.println(q(1));int x=lmax;for(int i=1;i<=n;i++)if(q(i)==x){System.out.print(a[i]+" ");//每个非降序列的第一个元素x--;} }}
4．程序运行示例与讨论
运行程序
12
48 1645 47 5246 36 2846 69 14 42
输出：
5.
16 4547 52 69
注意，所给序列长度为5的非降子序列可能有多个，这里只输出其中一个。
由上可知，在动态规划设计中，最优值可经递推得到，也可经递归得到。一般地，应用递推效率更高些，以下各案例的动态规划设计中均应用递推得最优值。
