class Solution {public:    /**     * @param A, B: Two strings.     * @return: The length of longest common subsequence of A and B.     */    int longestCommonSubsequence(string A, string B) {        // write your code here        int lena=A.length(),lenb=B.length();        int dp[lena][lenb];        memset(dp,0,sizeof(dp));        for(int i=0;i<lena;i++)        {            if(A[i]==B[0]) dp[i][0]=1;        }        for(int j=0;j<lenb;j++)        {            if(B[j]==A[0]) dp[0][j]=1;        }        for(int i=1;i<lena;i++)        {            for(int j=1;j<lena;j++)            {                if(A[i]==B[j]) dp[i][j]=dp[i-1][j-1]+1;                else dp[i][j]=max(dp[i-1][j],dp[i][j-1]);            }        }        return dp[lena-1][lenb-1];    }};

int longestCommonSubsequence(string A, string B){    int lena=A.length(),lenb=B.length();    int dp[lena][lenb];    int ret=0;    for(int i=0;i<lena;i++)    {        if(A[i]==B[0])        {            dp[i][0]=1;            ret=1;        }    }    for(int i=0;i<lenb;i++)    {        if(A[0]==B[i])        {            dp[0][i]=1;            ret=1;        }    }    for(int i=1;i<lena;i++)    {        for(int j=1;j<lenb;j++)        {            if(A[i]==B[j])            {                dp[i][j]=dp[i-1][j-1]+1;                ret=max(ret,dp[i][j]);            }            else dp[i][j]=0;        }    }    return ret;}

int minDistance(string word1, string word2) {        // write your code here        int lena=word1.length(),lenb=word2.length();        int dp[lena+1][lenb+1];        for(int i=0;i<=lena;i++)        dp[i][0]=i;        for(int i=0;i<=lenb;i++)        dp[0][i]=i;        for(int i=1;i<=lena;i++)        {            for(int j=1;j<=lenb;j++)            {                int del=dp[i-1][j]+1;                int ins=dp[i][j-1]+1;                int chan=dp[i-1][j-1]+(word1[i-1]==word2[j-1]?0:1);                dp[i][j]=min(min(del,ins),chan);            }        }        return dp[lena][lenb];    }