动态规划——最长非降顺序排列

http://www.360doc.com/content/13/0601/00/8076359_289597587.shtml

让我们沿用“入门”一节里那道简单题的思路来一步步找到“状态”和“状态转移方程”。假如我们考虑求A[1],A[2],…,A[i]的最长非降子序列的长度。当中i<N。那么上面的问题变成了原问题的一个子问题(问题规模变小了，你能够让i=1,2,3等来分析) 然后我们定义d(i)，表示前i个数中以A[i]结尾的最长非降子序列的长度。OK，对比“入门”中的简单题。你应该能够预计到这个d(i)就是我们要找的状态。假设我们把d(1)到d(N)都计算出来，那么终于我们要找的答案就是这里面最大的那个。状态找到了。下一步找出状态转移方程。

为了方便理解我们是怎样找到状态转移方程的，我先把以下的样例提到前面来讲。假设我们要求的这N个数的序列是：

5。3，4，8，6，7

依据上面找到的状态，我们能够得到：（下文的最长非降子序列都用LIS表示）

• 前1个数的LIS长度d(1)=1(序列：5)
• 前2个数的LIS长度d(2)=1(序列：3。3前面没有比3小的)
• 前3个数的LIS长度d(3)=2(序列：3，4；4前面有个比它小的3。所以d(3)=d(2)+1)
• 前4个数的LIS长度d(4)=3(序列：3，4，8。8前面比它小的有3个数，所以 d(4)=max{d(1),d(2),d(3)}+1=3)

OK，分析到这。我认为状态转移方程已经非常明显了。假设我们已经求出了d(1)到d(i-1)，那么d(i)能够用以下的状态转移方程得到：

d(i) = max{1, d(j)+1},当中j<i,A[j]<=A[i]

用大白话解释就是，想要求d(i)，就把i前面的各个子序列中，最后一个数不大于A[i]的序列长度加1，然后取出最大的长度即为d(i)。当然了。有可能i前面的各个子序列中最后一个数都大于A[i]。那么d(i)=1。即它自身成为一个长度为1的子序列。

//动态规划求最长非降子序列数组，res保存每项的非降子数列,返回值是最大长度
int lis(int A[], int n,int** res){
	int *d = new int[n];//保存每项的子序列长度
	int len = 1;
	for(int i=0; i<n; ++i)
	{
		d[i] = 1;//初始为1，为本身
		int pre;//保存之前非降位置
			for(int j=0; j<i; ++j)//找出它前面比它小的项，
			{
				if(A[j]<=A[i] && d[j]+1>d[i])
				{
					d[i] = d[j] + 1;
					pre=j;
				}
			}
			if(d[i]>len) len = d[i];//记录最大长度

		   //求每项的非降子数列
            res[i]=new int[d[i]];
			int j=0;
			printf("第%d项的非降子序列\n",i);
			for ( ;j<d[i]-1;j++)
			{//该项的非降子序列是前一项非降子序列加上本身
				res[i][j]=res[pre][j];
                printf("%d\n",res[i][j]);
			}
			res[i][j]=A[i];	
              printf("%d\n",res[i][j]);
	}
	delete[] d;
	return len;
}