算法分析：C语言实现动态规划之最长公共子序列

最长公共子序列问题

        下面的简单问题说明了动态规划的基本原理。在字母表一∑上分别给出两个长度为n和m的字符串A和B确定在A和B中最长公共子序列的长度。这里A = a₁a₂...an。的子序列是一个形式为a₁ka₂k...aik的字符串其中每个i都在1和n之间,并且1<i₁< i₂<…<ik≤n。例如如果∑= {x, y,z},A = zxyxyz和B= xyyzx那么xzy 同时是A和B的长度为3的子序列。然而它不是A和B最长的公共子序列因为字符串xyyz也是A和B公共的子序列由于这两个字符串没有比4更长的公共子序列因此A和B的最长的公共子序列的长度是4

        解决这个问题的-一种途径是蛮力搜索的方法:列举A所有的2^n个子序列对于每一个子序列在O( m)时间内来确定它是否也是B的子序列。很明显此算法的时间复杂性是O时间复杂度(m2²)是指数复杂性的。

        为了使用动态规划技术我们首先寻找--个求最长公共子序列长度的递推公式令A = a₁a₂...an和B= b₁b₂...bm令L[i,j]表示a₁a₂...ai和b₁b₂...bj的最长公共子序列的长度。

        注意、i和j可能是0此时a₁a₂...ai和b₁b₂...bj中的一个或同时可能为空字符串。即如果i =0或 j =o那么L[i,j]=0。很容易证明下面的观察结论。

        如果i和j都大于0那么

        1.若ai=bj, L[i,j]= L[ i-1,j - 1]+1;

·        2.若ai≠bj, L[i,j ]= max{L[i,j - 1],L[ i- 1,j] }。

最长公共子序列算法伪码

 

 最长公共子序列公式

 

 最长公共子序列解题思想

A的长度为5 B的长度为7
A字符串zxyyz
B字符串zyxzyxz
    0   z   y   x   z   y   x   z
0   0   0   0   0   0   0   0   0
z   0   0   0   0   0   0   0   0
x   0   0   0   0   0   0   0   0
y   0   0   0   0   0   0   0   0
y   0   0   0   0   0   0   0   0
z   0   0   0   0   0   0   0   0
z与z相遇即相等将左上角+1并将其余的比较大小1>0所以将其他的值变为1,即得到下图↓
    0   z   y   x   z   y   x   z
0   0   0   0   0   0   0   0   0
z   0   1   1   1   1   1   1   1
x   0   1   1   1   1   1   1   1
y   0   1   1   1   1   1   1   1
y   0   1   1   1   1   1   1   1
z   0   1   1   1   1   1   1   1
x与x相遇即相等y与y相遇即相等将左上角+1得2并将其余的比较大小2>1所以将其他的值变为2,即得到下图↓
    0   z   y   x   z   y   x   z
0   0   0   0   0   0   0   0   0
z   0   1   1   1   1   1   1   1
x   0   1   1   2   2   2   2   2
y   0   1   2   2   2   2   2   2
y   0   1   2   2   2   2   2   2
z   0   1   2   2   2   2   2   2
z与z相遇即相等y与y相遇即相等将左上角+1得3并将其余的比较大小3>2所以将其他的值变为3,即得到下图↓
    0   z   y   x   z   y   x   z
0   0   0   0   0   0   0   0   0
z   0   1   1   1   1   1   1   1
x   0   1   1   2   2   2   2   2
y   0   1   2   2   2   3   3   3
y   0   1   2   2   2   3   3   3
z   0   1   2   2   3   3   3   3
z与z相遇即相等将左上角+1得4没剩余得值了所以退出程序不用比较,即得到下图↓
    0   z   y   x   z   y   x   z
0   0   0   0   0   0   0   0   0
z   0   1   1   1   1   1   1   1
x   0   1   1   2   2   2   2   2
y   0   1   2   2   2   3   3   3
y   0   1   2   2   2   3   3   3
z   0   1   2   2   3   3   3   4

核心代码就那几行

for(i=1;i<=n;i++){
        for(j=1;j<=m;j++){
            if(a[i-1]==b[j-1])
                c[i][j]=c[i-1][j-1]+1;
            else
                c[i][j]=max(c[i][j-1],c[i-1][j]);
        }
    }

将数据一步一步的带入代码就可以理解了

 代码实现

#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#include <string.h>
void lcs();
int max(int a,int b);

int main()
{
    lcs();
    return 0;
}
int max(int a,int b)
{
    return a>b?a:b;
}
void lcs()
{
    int n,m,i,j;
    char *a,*b;
    printf("分别输入A和B的长度:");
    scanf("%d%d",&n,&m);

    a=(char *)malloc(n*sizeof(char));
    b=(char *)malloc(n*sizeof(char));
    int c[n+1][m+1];

    printf("输入A字符串");
        scanf("%s",a);
    getchar();
    printf("输入B字符串");
        scanf("%s",b);
    for(i=0;i<=n;i++)c[i][0]=0;
    for(j=0;j<=m;j++)c[0][j]=0;
    for(i=1;i<=n;i++){
        for(j=1;j<=m;j++){
            if(a[i-1]==b[j-1])
                c[i][j]=c[i-1][j-1]+1;
            else
                c[i][j]=max(c[i][j-1],c[i-1][j]);
        }
    }
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=m;j++)
        {
            printf("%d  ",c[i][j]);
        }
        printf("\n");
    }
    printf("\n%d\n",c[n][m]);
    printf("按任意键继续\n");
}

结果实现 

 

希望这对你有帮助