动态规划之LCS(最大公共子序列)

 1 #include <iostream>
 2 #include <string>
 3    using namespace std;
 4    int main(int argc, char **argv)
 5    {
 6        string str1 = "ABCBDAB";
 7        string str2 = "BDCABA";
 8 
 9        int x_len = str1.length();
10       int y_len = str2.length();
11 
12       int arr[50][50] = {{0,0}};
13 
14       int i = 0;
15       int j = 0;
16 
17       for(i = 1; i <= x_len; i++)
18       {
19           for(j = 1; j <= y_len; j++)
20           {
21               if(str1[i - 1] == str2[j - 1])
22               {
23                  arr[i][j] = arr[i - 1][j - 1] + 1;
24               }
25               else
26              {
27 
28                   if(arr[i][j - 1] >= arr[i - 1][j])
29                   {
30                       arr[i][j] = arr[i][j - 1];
31                   }
32                   else
33                   {
34                       arr[i][j] = arr[i -1][j];
35                   }
36               }
37 
38           }
39       }
40      for(i = 0 ; i <= x_len; i++)
41      {
42          for( j = 0; j <= y_len; j++)
43          {
44              cout << arr[i][j] << "  ";
45          }
46          cout << endl;
47      }
48      for(i = x_len, j = y_len; i >= 1 && j >= 1;)
49      {
50              if(str1[i - 1] == str2[j - 1])
51              {
52                  cout << str1[i - 1] << " ";//倒序打印的
53                  i--;
54                  j--;
55              }
56              else
57              {
58              //  if(arr[i][j -1] >= arr[i - 1][j])//打印：B A D B
59                  if(arr[i][j -1] > arr[i - 1][j]) //打印:A B C B
60                  {
61                      j--;
62                  }
63                  else
64                  {
65                      i--;
66                  }
67              }
68      }
69      cout << endl;
70      return 0;
71  }