NYOJ - 单调递增最长子序列(经典dp)

单调递增最长子序列

描述

求一个字符串的最长递增子序列的长度
如：dabdbf最长递增子序列就是abdf，长度为4

输入

第一行一个整数0<n<20,表示有n个字符串要处理
随后的n行，每行有一个字符串，该字符串的长度不会超过10000

输出

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

样例输入

3
aaa
ababc
abklmncdefg

样例输出

1
3
7

#include <stdio.h>
#include <string.h>int main(void)
{int n,dp[10001];char str[10001];scanf("%d",&n);while(n--){scanf("%s",str);int length = strlen(str);for(int i = 0; i < length; i++){dp[i] = 1;}for(int i = 1; i < length; i++){for(int j = 0; j < i; j++){if(str[i] > str[j]&&dp[i] < dp[j] + 1){dp[i] = dp[j] + 1;}}}int max = dp[0];for(int i = 0; i < length; i++){if(max < dp[i])max = dp[i];}printf("\n%d\n",max);}return 0;
}

假设f(i)是表示L中以ai为末位的元素最长单调递增序列，则递推方程如下：f(i) = max(f(i+1),f(i+2),f(i+3)......+ f(L)) + 1   这题已经AC，这里提供参考