nyoj--16--单调递增最长子序列

单调递增最长子序列

时间限制： 3000 ms  |  内存限制： 65535 KB 难度： 4

描述

求一个字符串的最长递增子序列的长度

如：dabdbf最长递增子序列就是abdf，长度为4

输入

第一行一个整数0<n<20,表示有n个字符串要处理

随后的n行，每行有一个字符串，该字符串的长度不会超过10000

输出

输出字符串的最长递增子序列的长度

样例输入

3
aaa
ababc
abklmncdefg      

样例输出

1
3
7      

思路：

动态规划的思想，把原问题分拆成若干相对简单的子问题，然后将其记忆化存储，以便下次需要同一个子问题解决的时候直接查表。针对这一题，假如要求的字符串长度为l，就先求出前1,2,3,4，. . .  个字符串的解，把他们结果存储在dp数组里面，以便后面用到的时候直接查表，当程序运行到第l个时，问题也就解决了。

代码：

 Java Code 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42

#include <iostream> #include<bits/stdc++.h> using namespace std; int  main() {     int  n;     int  dp[ 10005 ];     char  a[ 10005 ];    scanf( "%d" ,&n);     while (n--)    {        scanf( "%s" ,a);         int  l=strlen(a);         int  MAX=- 1 ;         for ( int  i= 0 ;i<l;i++)        {             ///求出前i个字符的结果            dp[i]= 1 ;             for ( int  j= 0 ;j<i;j++)            {                 ///查表计算                 if (a[j]<a[i]&&dp[i]<dp[j]+ 1 )                {                    dp[i]=dp[j]+ 1 ;                }            }        }         for ( int  i= 0 ;i<l;i++)        {             if (dp[i]>MAX)            {                MAX=dp[i];            }        }        printf( "%d\n" ,MAX);    }      return   0 ; }