动态规划步骤：

1、根据下面公式求出最大子序列的长度

C[i,j]为一个二维数组，用来保存子序列的长度

假设这两个序列分别是：X={A,B,C,B,D,A,B}    Y={B,D,C,A,B,A}

长度分别为        m            和   n

得出最长子序列的长度为4

2、根据回溯法求出最长子序列

i和j分别从m，n开始，递减循环直到i = 0，j = 0。其中，m和n分别为两个串的长度。

  ·如果str1[i] == str2[j]，则将str[i]字符插入到子序列内，i--，j--；

  ·如果str1[i] != str[j]，则比较L[i,j-1]与L[i-1,j]，L[i,j-1]大，则j--，否则i--；（如果相等，则任选一个）

接着我们来看一道题

题目描述：

给定一个字符串s，你可以从中删除一些字符，使得剩下的串是一个回文串。如何删除才能使得回文串最长呢？输出需要删除的字符个数

输入描述:

输入数据有多组，每组包含一个字符串s，且保证:1<=s.length<=1000.

输出描述:

对于每组数据，输出一个整数，代表最少需要删除的字符个数。

输入例子:

abcda 

google

输出例子:

2 

2

实现思想：

先保存字符串到str1

再保存字符串逆序后的结果到str2

求这两个序列的最大公共子序列，子序列的长度保存字二维数组C中

利用回溯法，求出最长公共子序列

#include 
     
      #include 
      
       #include 
       
        using namespace std;void Reverse(char* first,char* second){	char tmp;	while (first < second){		tmp = *first;		*first = *second;		*second = tmp;		++first;		--second;	}}int main(){	char s[1000];	while (cin >> s){		string str1(s);		/*string str2(s);		reverse(str2.begin(), str2.end());*/		Reverse(s,(s+str1.size()-1));		string str2(s);		//在str1、str2中找出最大公共子序列（LCS）		int m = str1.size();		int n = str2.size();		int* C = new int[ (m+1) * (n+1) ];//用来保存各子序列的长度		char* s1 = (char*)str1.c_str();		char* s2 = (char*)str2.c_str();		//填充二维数组C		for (int i = 0; i <= m; ++i){			for (int j = 0; j <= n; ++j){				if (i == 0 || j == 0){					C[i*(n+1) + j] = 0;				}				else{					if (*(s1 + i-1) == *(s2 + j-1)){						C [i*(n+1) + j] = C[(i-1)*(n+1) + j-1]+1;					}					else{						C[i*(n+1) + j] = (C[(i - 1)*(n+1) + j] > C[i*(n+1) + j - 1] ? C[(i - 1)*(n+1) + j] : C[i*(n+1) + j - 1]);					}				}				cout << C[i*(n + 1) + j] << " ";			}			cout << endl;		}		stack
        
          stmp;		for (int i = m,j = n; i >= 0&&j>=0;){			if (*(s1 + i-1) == *(s2 + j-1)){				stmp.push(*(s1+i-1));						--i;				--j;			}			else{				*(C + i*(n + 1) + j - 1) > *(C + (i - 1)*(n + 1) + j )? --j : --i;			}		}		int size = str1.size() - stmp.size();		cout << size<