hdu 1159Common Subsequence

http://acm.hdu.edu.cn/showproblem.php?pid=1159

Common Subsequence

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 13271    Accepted Submission(s): 5454

Problem Description

A subsequence of a given sequence is the given sequence with some elements (possible none) left out. Given a sequence X = <x1, x2, ..., xm> another sequence Z = <z1, z2, ..., zk> is a subsequence of X if there exists a strictly increasing sequence <i1, i2, ..., ik> of indices of X such that for all j = 1,2,...,k, xij = zj. For example, Z = <a, b, f, c> is a subsequence of X = <a, b, c, f, b, c> with index sequence <1, 2, 4, 6>. Given two sequences X and Y the problem is to find the length of the maximum-length common subsequence of X and Y.
The program input is from a text file. Each data set in the file contains two strings representing the given sequences. The sequences are separated by any number of white spaces. The input data are correct. For each set of data the program prints on the standard output the length of the maximum-length common subsequence from the beginning of a separate line.

 

Sample Input

abcfbc abfcab programming contest abcd mnp

 

Sample Output

4 2 0

被坑了几回，数组开小点吧，运行错误，数组开大点吧，又超内存。无语！

方法一：备忘录法，递归，存储已经计算的，防止重复计算，没那句话，果断超时啊。

#include<stdio.h>
#include<string.h>
#define INF -1
#define max(x,y) x>y?x:y
int len[1005][1005];
char str1[1000];
char str2[1000];
int lcs_len(int x,int y)
{
    if(len[x][y]!=INF) return len[x][y];//避免子问题的重复计算 
    if(x==0||y==0) len[x][y]=0;
    else if(str1[x-1]==str2[y-1]) len[x][y]=lcs_len(x-1,y-1)+1;//注意是 str1[x-1]==str2[y-1]字符串下标从0开始 
    else len[x][y]=max(lcs_len(x-1,y),lcs_len(x,y-1));
    return len[x][y];
}
int main()
{
    int len1,len2;
    
    while(~scanf("%s%s",str1,str2))
    {
        len1=strlen(str1);
        len2=strlen(str2);
        memset(len,INF,sizeof(len));
        printf("%d\n",lcs_len(len1,len2));
    }
}

动态规划，大大减小运行时间

#include<stdio.h>
#include<string.h>
#define max(x,y) x>y?x:y
char str1[1000];
char str2[1000];
int len[1005][1005];
int lcs_len(int x,int y)
{
    int i,j;
    for(i=0;i<=x;i++)
    len[i][0]=0;
    for(j=0;j<=y;j++)
    len[0][j]=0;
    for(i=1;i<=x;i++)
    {
        for(j=1;j<=y;j++)
        {
            if(str1[i-1]==str2[j-1]) len[i][j]=len[i-1][j-1]+1;
            else len[i][j]=max(len[i-1][j],len[i][j-1]);
        }
    }
    return len[x][y];
    
}
int main()
{
    int len1,len2;
    while(~scanf("%s%s",str1,str2))
    {
        len1=strlen(str1);
        len2=strlen(str2);
        printf("%d\n",lcs_len(len1,len2));
    }
    
    
}