在今年元旦，买了《算法导论》第三版，其实早在它还没有出版的时候，我就已经关注了，哈哈，于是就迫不及待地读了起来，尽管是在考试周。不过之后搁置了一段时间，这个月又开始读起来了。看到课后思考题15-2，231页，就写了一下。最长回文子序列，其具体问题如下：

回文是正序与逆序相同的非空字符，像civic,racecar等，还包括长度是1的字符串。求给定输入字符串的最长回文子序列。例如，给定输入character，算法返回carac。

假如给定字符是string,其长度为n，设定指针i、j分别指向string的头和尾，即是0<=i<j<n,初始时i=0，j=n-1。

解决方法如下：从字符串末尾开始判断是否有字符与当前指针i指向的string[i]相等，即判断string[i]与string[j]是否相等：

1. 如果不相等，则指针j向前挪一位，即j=j-1,直到j>=i，此时还不相等，则i向后移动，即i=i+1,该过程中始终保持i<j
2. 如果某位置的string[i]与string[j]相等，则参照公式，公式中递归定义了子问题的解:

p[i,j] = 1,如果j-i<2，又因为j>i,也就是j-i=1;

p[i,j] = 3,如果j-i=2;

p[i,j] = p[i+1,j-1]+2,如果j-i>2;

其中p[i,j]表示字符串string中以第i个字符开始、第j个字符结束的串的最长回文子序列长度，当j-i=1时，说明字符串中只有两个字符，而这两个字符又相等，明显p[i,j]应该为1；当j-i=2时，说明字符串有3个字符，两个相等的字符中夹了一个其他字符，明显p[i,j]也为2+1=3；当j-i>2时，则利用子问题的解来递归定义此时问题的解。

其实，这个问题使用了动态规划的解题方法，找出问题的最优子结构性质，在利用子问题来递归定义原问题（使用子问题来表示原问题的解），把解决原问题的解建立在子问题的基础之上。

在实现动态规划的算法时，通常有2种实现思路，一是自底向上，也就是先求解小的子问题，然后慢慢扩大子问题的规模再求解，而求解规模较大的子问题时有需要使用到规模较小的子问题，所以说是自底向上，不过要仔细考虑具体实现时的顺序；而是带备忘的自定向下的递归方法，与一般递归方法不同的是，如果不用重复求解已经解过的子问题，只要直接查表即可。

其中在求解最优化问题的时候，通常涉及到构造最优解，此处是使用数组mark记录下在比较过程中相等字符的位置，分别是i，j。

实现代码如下，这是带备忘的自定向下的递归实现：

1. #include <string> 
2. using namespace std; 
3.  
4. size_t huiwen_length(string &x,size_t i,size_t j); 
5. void print_huiwen(string &x,size_t * mark); 
6.  
7. size_t p[20][20]; 
8. size_t mark[20]; 
9. void main(int argc, char **argv){ 
10.     string x("tccaivic"); 
11.     huiwen_length(x,0,x.size()-1); 
12.     print_huiwen(x,mark); 
13. } 
14.  
15. size_t huiwen_length(string &x,size_t i,size_t j){ 
16.     if (p[i][j]>0) 
17.     { 
18.         return p[i][j]; 
19.     } 
20.      
21.     for (size_t begin=i,end=j;i<j;i++,j=end;) 
22.     { 
23.         for (;i<j;) 
24.         { 
25.             if (x[i]==x[j]) 
26.             { 
27.                 if (j-i>2)//j-i>2 
28.                 { 
29.                     p[begin][end]=huiwen_length(x,i+1,j-1)+2;//p[i][j] = p[i+1][j-1]+2; 
30.  
31.                 }else if (j-i==2)//j-i==2相当于相等的2个元素之间夹了一个元素 
32.                 { 
33.                     p[begin][end]=3; 
34.                     mark[i+1]=1;//设置夹了那个 
35.                     //return 3;//p[i][j]=3; 
36.                 }else {
    //0<j-i<2,即是j-i==1 
37.                     p[begin][end]=2; 
38.                     //return 2;//p[i][j]=2; 
39.                 } 
40.                 mark[i]=1; 
41.                 mark[j]=1; 
42.                 return p[begin][end]; 
43.             }else{ 
44.                 j--; 
45.             }        
46.         } 
47.     } 
48.     return 0; 
49. } 
50.  
51. void print_huiwen(string &x,size_t * mark){ 
52.     cout<<"huiwen of "<<x<<":"; 
53.     for (size_t i=0;i<x.size();i++) 
54.     { 
55.         if (mark[i]==1) 
56.         { 
57.             cout<<x[i]; 
58.         } 
59.     } 
60.     cout<<endl; 
61. } 

动态规划适用于求解最优化问题，掌握了该方法可以更好地增强自己的算法能力。