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