【poj1458】Common Subsequence || nyoj36 (动态规划)

Categories: 数据结构和算法
Tags: ,
Comments: No Comments
Published on: 2011 年 04 月 20 日

状态转移方程:
if(st1[i]==st2[j])
res[i+1][j+1]=res[i][j]+1;
else
res[i+1][j+1]= res[i][j+1]>res[i+1][j] ?res[i][j+1]:res[i+1][j] ;
res[i][j]表示字符串字串st1[0-i],st2[0-j]的公共子序列长度。

#include<cstdio>  
#include <string>  
#include <iostream>  
#include <cstring>  
#include <algorithm>  
using namespace std;  
int res[301][301];  
int main()  
{  
    freopen("1.txt","r",stdin);  
    string st1,st2;  
    while(cin>>st1>>st2)  
    {  
        memset(res,0,sizeof(res));  
        for (int i=0;i<st1.length();i++)  
        {  
            for (int j=0;j<st2.length();j++)  
            {  
                if(st1[i]==st2[j])  
                    res[i+1][j+1]=res[i][j]+1;  
                else res[i+1][j+1]= res[i][j+1]>res[i+1][j] ?res[i][j+1]:res[i+1][j] ;  
            }  
        }  
        cout<<res[st1.length()][st2.length()]<<endl;  
    }  
}  

我猜你可能也喜欢:

No Comments - Leave a comment

Leave a comment

电子邮件地址不会被公开。 必填项已用*标注

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>


Welcome , today is 星期二, 2017 年 10 月 24 日