DP问题之最长非降子序列

时间：2011-04-29 来源：风行者乐园

问题描述：在一个无序的序列a1,a2,.....,am里，找到一个最长的序列，满足ai<=aj...<=ak; 且i<j<k;

问题分析：如果前i-1个数中的最长非降子序列的最后一个数是ak;那么下一步就是在求前k-1个数中的的最长非降子序列；

因此我们可以设计一个状态opt[j]表示前i个数中用到a[i]所构成的最优解。

那么决策就是在前i-1个数中找到最大的opt[j] 使得a[j]<=a[i]，那么opt[j]+1 就是opt[i]的值;

方程可以这样表示：

　　　　　　max[opt[j]] a[i] < a[j] && 0<=j<i

opt[i] =

　　　　　　max[opt[j]]+1 a[i] >= a[j] && 0<=j<i

下面是一C测试代码:

#include <stdio.h>
#include <stdlib.h>

int main()
{   
    int seq[10] = {4,5,7,8,3,2,6,7,33,4};
    int opt[10], i, j, max = 0;
    for(i=0; i<10; i++)
        opt[i] = 0;
    opt[0] = 1;  //只有一个数时最长非降序列长度为1
    for(i=1; i<10; i++)
        for(j=0; j<i; j++)
        {
            if(seq[j]<=seq[i] && opt[j]+1>opt[i])
            {
                opt[i] = opt[j]+1;
            }
        }
    for(i=0; i<10; i++)
        if(opt[i] > max)
            max = opt[i];
    printf("max:%d\n", max);
    return 0;
}