1 class Solution {
 2 public:
 3     int longestCommonSubsequence(string text1, string text2)
 4     {
 5         const int text1_len = text1.size();
 6         const int text2_len = text2.size();
 7         int dp[text1_len+1][text2_len+1];
 8         memset(dp,0,sizeof(dp));
 9         //base case
10         for(int i = 1;i<=text1_len;++i)
11         {
12             dp[i][0] = 0;
13         }
14         for(int j = 1;j<=text2_len;++j)
15         {
16             dp[0][j] = 0;
17         }
18         //state move
19         for(int i = 1;i<=text1_len;++i)
20         {
21             for(int j = 1;j<=text2_len;++j)
22             {
23                 if(text1[i-1]==text2[j-1])
24                 {
25                     dp[i][j] = dp[i-1][j-1]+1;
26                 }
27                 else
28                 {
29                     dp[i][j] = max(dp[i][j-1],dp[i-1][j]);
30                 }
31             }
32         }
33         //last state as target
34         return dp[text1_len][text2_len];
35     }
36 };

class Solution {
public:
    int minDistance(string word1, string word2)
    {
       if(word1.empty()&&word2.empty()){
           return 0;
       }
       else if(word1.empty())
       {
           return word2.size();
       }
       else if(word2.empty())
       {
           return word1.size();
       }
       else
       {
          const int word1_len = word1.size();
          const int word2_len = word2.size();
          int dp[word1_len][word2_len];//dp[i][j] word1[0:i]到word2[0:j]的最短编辑距离
        //  memset(dp,0,sizeof(dp));
           for(int i = 0;i<word1.size();++i)
          {
                for(int j = 0;j<word2.size();++j)
                {
                    int one,two,three;
                    //base case
                    if(i==0&&j==0)
                    {
                        one = 0; //dp[i-1][j-1]
                        two = 1;//dp[i-1][j]
                        three = 1;//dp[i][j-1]
                    }
                    else if(i==0) //j!=0
                    {
                        one = j; //dp[i-1][j-1]
                        two = j+1;//dp[i-1][j]
                        three = dp[i][j-1] ;//dp[i][j-1]
                    }
                    else if(j==0) //j!=0
                    {
                        one = i; //dp[i-1][j-1]
                        two = dp[i-1][j];//dp[i-1][j]
                        three = i+1;//dp[i][j-1]
                    }
                    // normal case 
                    else 
                    {
                        one = dp[i-1][j-1];
                        two = dp[i-1][j];
                        three = dp[i][j-1];
                    }
                    //state move
                    if(word1[i]==word2[j])
                    {
                        dp[i][j] = one;
                    }
                    else
                    {
                        dp[i][j] = min(min(two+1,three+1),one+1);
                    }
                }
           }
           // the last state  
           return dp[word1_len-1][word2_len-1];
       }
    }
};