最长公共子串（LCS）

动态规划的代表作：
其实，DP就是把递归写的程序改成带备忘记录的，或者至底而上的来避免重复计算同一子问题而已。。。。。
 1 #include <iostream>
 2 
 3 using namespace std;
 4 
 5 int main()
 6 {
 7     int a[9]={9999,1,0,0,1,0,1,0,1};
 8     int b[10]={-9999,0,1,0,1,1,0,1,1,0};
 9 
10     int i,j;
11 
12     char s[9][10];//记录移动方向
13     int c[9][10];//记录从a[i]b[j]的最长子串的长度/记录移动
14 
15     for(i=0;i<9;i++)
16         c[i][0]=0;
17     for(j=0;j<10;j++)
18         c[0][j]=0;
19 
20     for(i=1;i<9;i++)
21     {
22         for(j=1;j<10;j++)                                      // 共三种情况： 
23         {                                                                           // 1：若a[i]==b[j]：最长子串就是c[i][j]=c[i-1][j-1]+1；
24             if(a[i]==b[j])
25             {
26                 c[i][j]=c[i-1][j-1]+1;
27                 s[i][j]='A';
28             }
29             else if(c[i-1][j]>=c[i][j-1])
30             {                                                                      //   2：如果不相等，那就是c[i-1][j]与c[i][j]=c[i][j-1]里较大的一个
31                 c[i][j]=c[i-1][j];
32                 s[i][j]='B';
33             }
34             else
35             {                                                           //          3：若某个字串长度为0,子串长度也为0
36                 c[i][j]=c[i][j-1];
37                 s[i][j]='C';
38             }
39         }
40     }
41 
42     cout<<c[8][9]<<endl;
43 
44     i=8;j=9;
45     int k[10];
46     int _end=0;
47     while(i!=0&&j!=0)
48     {
49         if(s[i][j]=='A')
50         {
51            k[_end]=a[i];
52            _end++;
53            i--;
54            j--;
55         }
56         else if(s[i][j]=='B')
57         {
58             i--;
59         }
60         else if(s[i][j]=='C')
61         {
62             j--;
63         }
64     }
65 
66     for(int i=_end-1;i>=0;i--)
67         cout<<k[i]<<" ";
68 
69 
70     return 0;
71 }