3aaaababcabklmncdefg

137

? ?思路：

? ?题意简明易懂，所以不作解释。最基本的动态规划题，设 i 为当前位置，max[ i ]为当前位置的单调递增的最大长度，则max[ i ] = max{max[ i-1 ],max[ i-2 ],max[ i-3 ]......max[ 0 ]}+1,故算当前最大长度时，应设另外一个变量j从0开始到i进行遍历，找到最大的一项max [ j ]进行+1再赋值于max[ i ]。故 i 应从1遍历到length。数组中最大max[ i ]值即为最长递增子序列的长度。（一开始全部max数组的值都初始化为1）

? AC：

#include<stdio.h>#include<string.h>int main(){   int n,length,i,j,m;   char s[10005];   int max[10005];   scanf("%d",&n);   while(n--)   {   scanf("%s",s);   length=strlen(s);   for(i=0;i<length;i++)     max[i]=1;//初始化为1不为0，因为最长子序列长度最坏的情况就是1//即不存在这样的单调递增序列，每个数都是一个单独的递增长度，长度为1     m=1;//同理，最大值也应该是1，记得m的初始化在循环内进行，非循环外//从前递推到后，i在前j在后，故判断条件应该是s[j]>s[i]   for(i=1;i<length;i++)   {   for(j=0;j<i;j++)    if(s[i]>s[j])     max[i]=max[i]>max[j]+1?max[i]:max[j]+1;//每个max[i]都为当前位置i为止的最大长度情况，但这不代表max数组最后一个值肯定为最大   if(max[i]>m) m=max[i];  //在最大值，无需另外开个循环再判断   }   printf("%d\n",m);   }   return 0;}

? ?总结：

? ?在学新知识的时候应该找相对简单的题来练练手，以至于不生疏，于是大晚上的拿了道动态规划最基本的题来做。需要注意的地方还是有的，越简单出错的几率就越大，考虑循环边界的问题，还有最大值的初始化问题，这是之前一直出错的地方。