动态规划经典最长公共子序列 poj1159

最新推荐文章于 2025-06-03 13:16:34 发布

Yonggie

最新推荐文章于 2025-06-03 13:16:34 发布

阅读量370

点赞数

分类专栏：数据结构

数据结构专栏收录该内容

59 篇文章

订阅专栏

出处http://blog.csdn.net/v_july_v/article/details/6695482

帮我稍微理解了这个思想。

哎~我就是传说中的无脑儿啊！

一个序列X，一个序列Y，

X的下标用i，Y的下标用j，

Xi表示从第一个元素到第i个元素的这个序列。

Yj表示从第一个元素到第j个元素的序列。

xi表示X序列的第i个元素，yj表示Y序列的第j个元素。

我们把序列Xn和Ym的最长公共子序列的长度表示为F(n,m)。

先说一下递归的做法。

假设现在我们想要求F(i,j)，

1.如果xi==yj，那么这个xi（或者是yj）一定是Xi和Yj的最长公共子序列的结尾数字，好，继续往下递归求X(i-1)和Y(j-1)的最长公共子序列长度，长度加1就是F(i,j)的值。

2.如果xi！=yj，那么这个 xi 一定不是Xi和Yj的最长公共子序列的结尾数字，那么结尾的数字在前面，也就是F(i,j)与F(i-1,j)或者与F(i,j-1)相比长度并没有增加，那么我想要他们中最大的啊，于是F(i,j)=max（ F(i-1,j)，F(i,j-1)）。好，那么递归求F(i-1,j)和F(i,j-1)的值。

（你想要的最终结果就把i换成X的长度，j换成Y的长度就是了）

处理一下边界。

那显然就是i==0或者j==0的时候了。F(0,j)或者F(i,0)都是0（这个是显然的吧~你一个什么都没有的序列和任意序列的公共子序列显然是0啊），这样可以返回值了。

我用伪代码写一下啊（其实也不算伪代码……）

这个的前提是你已经读入了X这个序列和Y这个序列了啊。

xi表示X序列的第i个元素，yj表示Y序列的第j个元素。

想求F(i,j):

if( xi==yj ) return F(i-1,j-1)+1;

else return max ( F(i-1,j) , F(i,j-1) ); /*也就是xi！=yj的时候*/

OK,那么我们发现有很多时候有些值是重复计算的。处理方法显然有两种啦，一种是记忆化搜索，一种是动态规划了（倒着这个过程来呗）。

其实网上还有很多大牛，我就不啰嗦那些名词了，什么子问题重复什么的……我只是理解而已，想让我一板一眼地讲出来还是真有难度，想知道具体的可以看他们更加专业化的讲解。

我只说动态规划的。

既然后面的状态需要求出前面的状态，那我何不从前面的状态开始求起，递推出后面的状态呢？

初始的状态是F(i,0)=0而且F(0,j)=0；

那么递推开始了，关键的条件还是不变的。

现在我们想求F(i,j)（它可以由前面的状态推出来哦！注意现在是递归过程的逆着来了,递归是去找前面的状态，动态规划是从底层的状态推出来高层的状态）

if(xi==yj) F(i,j) = F ( i-1 , j-1 ) + 1;

else F(i,j)=（ F(i-1,j) ， F(i,j-1)）；

那么一路递推下去，推到两个序列的长度即可。

因为F有两个参数，所以在用代码实现的时候要用二维数组来实现。这里我用了dp数组来表示F这个函数。

好啦终于可以上代码啦。

注意下标的处理。

AC代码

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std;
const int maxn=1e3+10;
const int inf=1e9+10;

int dp[maxn][maxn];
int main()
{
    
    //初始化F(i,0)或者F(0,j)为0；
    memset(dp,0,sizeof(dp));
    char str1[maxn];
    char str2[maxn];
    scanf("%s %s",str1,str2);

    int len1=strlen(str1);
    //cout<<"len is "<<len1<<endl;
    int len2=strlen(str2);

    //从第一个数字开始递推，推到最后一个数字。
    for(int i=1;i<=len1;i++)
    {
        for(int j=1;j<=len2;j++)
        {

	    //注意这里字符串的下标并不是1、2、3、4、5而是0、1、2、3、4所以要处理好。
            if(str1[i-1]==str2[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[len1][len2]<<endl;
    }
}

希望这次南宁的邀请赛能拿个奖。吐舌头也希望我这个兴趣能一直保持下去咯~