动态规划:最长公共子序列(C/C++)

最长公共子序列(题目:2129):

            给出两个字符串，求出这样的一个最长的公共子序列的长度:

    子序列中的每一个字符都能在两个原串中找到,而且每个字符的先后顺序和原串中的先后顺序和原串中的先后顺序一致。 

举例：

    Sample Input:

    abcfbc abfcab

    programming contest

    abcd mnp

    Sample Output:

    4

    2

    0

    输入两个串s1,s2,

    设MaxLen(i,j)表示：

            s1的左边i个字符形成的子串,与s2左边的j个字符形成的子串的最长公共子序列的长度(i,j从0开始算),MaxLen(i,j)就是本题的"状态"

假定 len1 = strlen(s1), len2 = strlen(s2),那么题目就是要求 MaxLen(len1,len2)

显然(边界条件)：

    MaxLen(n,0) = 0 ( n = 0...len1 )

    MaxLen(0,n) = 0 ( n = 0...len2 )

递归公式：

    if(s1[i-1] == s2[j-1]) //s1的最左边字符是s1[0]

        MaxLen(i,j) = MaxLen(i-1,j-1) + 1;

    else

        MaxLen(i,j) = Max(MaxLen(i,j-1),MaxLen(i-1,j));

时间复杂度O(mn) m,n是两个字符串长度

S1[i-1] != s2[i-2]时,MaxLen(S1,S2)不会比MaxLen(S1,S2(j-1))

和MaxLen(S1(i-1),S2)两者之中任何一个小,也不会比两者都大。

当然,以上讨论直接可以用递归实现,而我们今天要使用递推来实现:

当我们用递推来写的时候,用列表寻找for循环的规律(动态转移方程),看表如下:(横向是i,纵向是j)

 思想探讨:

                        从表上我们可以看出,每一个dp[i][j]所对应的表格内容判断是否加一的时候,都与它的左上角的一格有关, 如果两个相同则把左

        上角的一格加一赋值到这一格即可,如果不同的话看它的左边一格,和上边一格,取最大,这样以来的递推下去就可以再最后一格的时候,得到

        最长公共子序列的长度大小,即直接打印dp[s1.size][s2.size].

C语言参考代码:

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int main()
{
    char s1[1000];char s2[1000];
    scanf("%s",s1);
    scanf("%s",s2);
    int lens1=strlen(s1);int lens2=strlen(s2);
    int dp[lens1+1][lens2+1];
    //保险起见,我们要把纵轴和横轴的第一行全赋值0,因为我们的递推是从第一格开始就是判断左上角,左边,上边的值,提前赋值0,防止数组越界
    for(int i=0;i<=lens1;i++)
    {
        dp[i][0]=0;
    }
    for(int i=0;i<=lens2;i++)
    {
        dp[0][i]=0;
    }
    for(int i=1;i<=lens1;i++)
    {
        for(int j=1;j<=lens2;j++)
        {
            if(s1[i-1]==s2[j-1])//注意细节
            {
               dp[i][j]=dp[i-1][j-1]+1;
            }
            else
            {
                dp[i][j]=dp[i-1][j]>dp[i][j-1]?dp[i-1][j]:dp[i][j-1];
            }
    }
}
    printf("%d",dp[lens1][lens2]);
}

 C++参考代码:

#include <iostream>
using namespace std;
int dp[1005][1005];
int main(){
    string s1,s2;
    cin>>s1>>s2;
    for(int i=1;i<=s1.size();i++){//s1.size就是字符串长度
        for(int j=1;j<=s2.size();j++){
            if(s1[i-1]==s2[j-1]){
                dp[i][j]=dp[i-1][j-1]+1;
            }else{
                dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
            }
        }
    }
    cout<<dp[s1.size()][s2.size()]<<endl;
    return 0;
}

能看懂上面的代码,转换成Java都是有手就行的事情!

多练习,多思考,多在纸上画画表格,推导状态转移方程,需要多练各种各样的DP问题,加油