hdu1159（最長公共子序列，滾動數組）

狀态轉移方程為：dp[i][j]=dp[i-1][j-1]+1(s1[i]==s2[j])；dp[i][j]=max(dp[i-1][j],dp[i][j-1])(s1[i]!=s2[j])

此題字元串的長度不是很大，是以不會超記憶體

代碼如下：

#include<iostream>
#include<algorithm>
#include<string>
#include<stack>
#include<queue>
#include<map>
#include<stdio.h>
#include<stdlib.h>
#include<ctype.h>
#include<time.h>
#include<math.h>

#define eps 1e-9
#define N 1000  
#define P system("pause")
using namespace std;
char s1[N],s2[N];
int dp[N][N];

int main()
{
//freopen("input.txt","r",stdin);
//freopen("output.txt","w",stdout);cc
    int i,j;
    while(scanf("%s%s",s1,s2)!=EOF)
    {
          int len1=strlen(s1);
          int len2=strlen(s2);
          memset(dp,0,sizeof(dp));
          for(i=1;i<=len1;i++)
             for(j=1;j<=len2;j++)
             {
                   if(s1[i-1]==s2[j-1])
                       dp[i][j]=dp[i-1][j-1]+1;
                   else
                       dp[i][j]=max(dp[i][j-1],dp[i-1][j]);                    
             }                               
          printf("%d\n",dp[len1][len2]);
    }                         
//    P;                               
    return 0;    
}
           

擴充：

當字元串的長度很大時，開二維dp數組就會超記憶體，是以要用滾動數組

代碼如下：

#include<iostream>
#include<algorithm>
#include<string>
#include<stack>
#include<queue>
#include<map>
#include<stdio.h>
#include<stdlib.h>
#include<ctype.h>
#include<time.h>
#include<math.h>

#define eps 1e-9
#define N 1000  
#define P system("pause")
using namespace std;
char s1[N],s2[N];
int dp[N],pre[N];

int main()
{
//freopen("input.txt","r",stdin);
//freopen("output.txt","w",stdout);cc
    int i,j;
    while(scanf("%s%s",s1,s2)!=EOF)
    {
          int len1=strlen(s1);
          int len2=strlen(s2);
          memset(dp,0,sizeof(dp));
          memset(pre,0,sizeof(pre));
          for(i=1;i<=len1;i++){
             for(j=1;j<=len2;j++)
             {
                   if(s1[i-1]==s2[j-1])
                       dp[j]=pre[j-1]+1;
                   else
                       dp[j]=max(dp[j-1],pre[j]); 
                   pre[j-1]=dp[j-1];     //pre記錄i-1行  dp記錄i行                
             }                 
             pre[len2]=dp[len2];         //不要忘記最後一個字元
          }              
          printf("%d\n",dp[len2]);
    }                         

 //   P;                               
    return 0;    
}