UVA 10405 Longest Common Subsequence --经典DP

时间：2023-12-24 10:17:01

最长公共子序列，经典问题。算是我的DP开场题吧。

dp[i][j]表示到s1的i位置，s2的j位置为止，前面最长公共子序列的长度。

状态转移：

dp[i][j] = 0                                       (i == 0 || j == 0)

dp[i][j] = dp[i-1][j-1] + 1                   (s1[i] == s2[j]) (此字符相等，说明此时最长公共子序列的长度等于他们之前的LCS（简称）长度加上这个相等的字符（长度为1）)

dp[i][j] = max(dp[i-1][j],dp[i][j-1])      (s1[i] != s2[j]) (此字符不相等，说明此时LCS为i减小一位再求LCS的长度以及j减小一位再求LCS的长度的最大值。即为LCS）

代码：

#include <iostream>

#include <cstdio>

#include <cstring>

#include <cmath>

#include <algorithm>

#include <string>

using namespace std;

#define N 1007

int dp[N][N],n;

int main()

{

    int m,n,i,j;

    string s1,s2;

    while(getline(cin,s1) && getline(cin,s2))

    {

        m = s1.length();

        n = s2.length();

        s1 = " " + s1;

        s2 = " " + s2;

        for(i=;i<=m;i++)

            dp[i][] = ;

        for(j=;j<=n;j++)

            dp[][j] = ;

        for(i=;i<=m;i++)

        {

            for(j=;j<=n;j++)

            {

                if(s1[i] == s2[j])

                    dp[i][j] = dp[i-][j-] + ;

                else

                    dp[i][j] = max(dp[i-][j],dp[i][j-]);

            }

        }

        printf("%d\n",dp[m][n]);

    }

    return ;

}

（注意这里用string的话，不能cin>>s1>>s2,虽然我也不知道哪里不对。还是用getline保险一点。如果是字符数组的话，就用gets或者scanf都可以。）

相关文章