这是到动态规划的题目，属于有顺序的0 1 背包问题；

代码：

1 #include
     
       2 #include
      
        3  4 int d[20][100000];  //d[i][j] 5 int a[20]; 6 int N; 7  8 int max(int a, int b) 9 {10     return a>b?a:b;11 }12 13 int solve(int i,int high)14 {15     if(d[i][high]>=0)16         return d[i][high];17     if(i==N)18     {19         if(a[i]
      
     

但这个代码提交会得到RE，至于为什么可能是记忆话搜索对这个的复杂度减小的比较小，所以递归深度太深，造成堆栈溢出。

我想多了，不是这个原因，是我没有注意到下标越界了。

AC代码：

1 #include
     
       2 #include
      
        3  4 int d[22][1000];  //d[i][j] 5 int a[22]; 6 int N; 7  8 int max(int a, int b) 9 {10     return a>b?a:b;11 }12 13 int solve(int i,int high)14 {15     if(d[i][high]>=0)16         return d[i][high];17     if(i==N)18     {19         if(a[i]
      
     

 我不知道原来这种问题叫 最长递增子序列问题  我还给他起了个（顺序0 1 背包问题），我这就透过本质起的名字。

最长字串问题  （NYOJ - 17）

AC代码：

#include
      
       #include
       
        #include
        
         int d[10002][180];char a[10002];int N;int max(int a, int b){    return a>b?a:b;}int dp(int i, char c){    if(d[i][c]>=0)        return d[i][c];    if(i==N-1)    {        if(a[i]>c)            return d[i][c] = 1;        else            return d[i][c] = 0;    }    if(a[i]>c)        return d[i][c]=max(dp(i+1,c),dp(i+1,a[i])+1);    else        return d[i][c]=dp(i+1,c);}int main(){    int T;    scanf("%d",&T);    while(T--)    {        memset(d,-1,sizeof(d));        scanf("%s",a);        N = strlen(a);        printf("%d\n",dp(0,0));    }    return 0;}