欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

LintCode 77. 最长公共子序列(C++ 动态规划)

程序员文章站 2022-07-12 14:36:32
...

从暴力搜索到递归,暴力搜索超时,主要用于找寻递归式,即动态规划的表达式

class Solution {
public:
    /**
     * @param A: A string
     * @param B: A string
     * @return: The length of longest common subsequence of A and B
     */
   
    //两个指针分别指向两个数组,
    //当元素相等时,子序列长度加1,且两个指针均后移
    //如元素不等时,该元素不能作为子序列,移动其中一个指针
    
    
    //选到A中的第i个元素,B中的第i个元素 时的最大子序列
    
    /*
    int search(int Ai,int Bi,string A, string B,vector<vector<int>>mem)
    {
        if(Ai>=A.length()||Bi>=B.length())
            return INT_MIN;
        if((Ai==A.length()-1)&&(Bi==B.length()-1))
            return 0;
        
        if(mem[Ai][Bi]>=0)
            return mem[Ai][Bi];
            
        int tmp1=0;
        if(A[Ai]==B[Bi])
             tmp1=search(Ai+1,Bi+1,A,B,mem)+1 ;//可以作为公共子序列,长度加1,两者都继续往后搜索
        int tmp2=search(Ai,Bi+1,A,B,mem);//不能作为公共子序列,其中一个往后继续搜索
        int tmp3=search(Ai+1,Bi,A,B,mem); //不能作为公共子序列,其中一个往后继续搜索 
        mem[Ai][Bi]=max(tmp1,max(tmp2,tmp3));
        return mem[A.length()-1][B.length()-1];
    }
     
     */
    int longestCommonSubsequence(string &A, string &B) {
        // write your code here
        if(A.length()==0||B.length()==0)
            return 0;
        
        //mem[i][j]:数组A的长度为i,数组B的长度为j,的最大子序列
        vector<vector<int>>mem(A.length(),vector<int>(B.length()));
        int n=mem.size();
        int m=mem[0].size();
        
        for(int j=0;j<m;j++)
        {
            if(A[0]==B[j])
                mem[0][j]=1;
            else mem[0][j]=0;
        }
        
        for(int i=1;i<n;i++)
        {
            if(A[i]==B[0])
                mem[i][0]=1;
            else mem[i][0]=0;
            for(int j=1;j<m;j++)
            {
                mem[i][j]=max(mem[i][j-1],mem[i-1][j]);
                if(A[i]==B[j])//这个条件忘写了,害我调试半天!
                    mem[i][j]=max(mem[i-1][j-1]+1,mem[i][j]);
            }
        }
        
        return mem[n-1][m-1];
    
    } 
};
相关标签: 常用算法