UVA 10405 Longest Common Subsequence --经典DP

最长公共子序列，经典问题。算是我的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=1;i<=m;i++)
            dp[i][0] = 0;
        for(j=0;j<=n;j++)
            dp[0][j] = 0;
        for(i=1;i<=m;i++)
        {
            for(j=1;j<=n;j++)
            {
                if(s1[i] == s2[j])
                    dp[i][j] = dp[i-1][j-1] + 1;
                else
                    dp[i][j] = max(dp[i-1][j],dp[i][j-1]);
            }
        }
        printf("%d\n",dp[m][n]);
    }
    return 0;
}

View Code

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

UVA 10405 Longest Common Subsequence --经典DP

推荐阅读