LintCode 77. 最長共通サブシーケンス(C++ダイナミックプランニング)

暴力検索から再帰へ、暴力検索がタイムアウトし、主に再帰式、すなわち動的計画の表現を探すために使用される.

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>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];
    
    } 
};