最近遇到两个题目，比较有意思，由于两个题目的描述比较相似，在这里就一起说了，做一个比较

题目一：给定一个字符串，给该字符串添加一些字符，使其成为一个回文串，求需要添加的最少字符数，并求出添加字符后回文串的样子，如果有多个这样的回文串，只用返回其中一个即可

比如： str="AB"  那么，只用在 "A" 之前添加一个B，就可以形成回文  “ABA”

            str="A"    那么，不用添加,就已经是回文了

            str="ACDC" ， 那么在最后添加一个A就可以形成回文 "ACDCA"

思路：此题可以用动态规划进行操作，开一个数组dp[i][j], 表示要想使得 i  到  j 这段长度的字符串成为回文字符串，至少需要添加多少个字符,我们都知道动态规划需要分析通项公式，但是有一些不需要依赖其他

元素，可以独立推出来的值，我们需要单独处理：当i=j, 即字符串的长度为1时，这个字符串肯定是回文的，当字符串长度大于2时，有如下情况

(1)如果 i 和 j 相邻 , 并且str[i]==str[j]， 那么dp[i][j]=0, 如果 str[i] != str[j]  ,那么dp[i][j]=1;表示需要添加一个字符串

(2)如果 i 和 j 不相邻，  但str[i]==str[j]， 那么dp[i][j]=dp[i+1][j-1],表示只要 i 和 j 内部的字符串组成回文后，i 到 j 这部分就自然成为回文了 ，如果 str[i] != str[j]  ,那么dp[i][j]=min(dp[i][j-1],dp[i+1][j])+1, 表示只要单边形成回文串后，另一边添加对边的值即可成为回文，此时有两种补法，所以需要取最小的

注意到上面动态规划时，dp[i][j] = dp[i+1][j-1]等表达式，隐含的条件是，外面的值需要依赖里面的值，所以我们在填表时，需要注意由里面向外面扩散

求出dp表以后，再按照两边向中间的顺序进行还原，就可以还原出回文字符串了，比如，当str[left] 和 str[right] 相等时，直接复制到copy[ ] 数组中去，如果str[left] 和 str[right] 不相等，那么就比较dp[left][right-1] 和 dp[left][right-1] 的值，看看补哪边需要的字符串最少，具体代码如下

1 import java.util.ArrayList; 2 import java.util.Deque; 3 import java.util.LinkedList; 4 import java.util.Scanner; 5 import java.util.Stack; 6 /*给定字符串,添加最少成为回文字符串,采用动态规划*/ 7 public class Main { 8     public static void main(String[] args) { 9         Scanner scan = new Scanner(System.in);10         String str = scan.nextLine();11         char s[] = str.toCharArray();12         int dp[][] = new int[s.length][s.length];   //dp[i][j] 表示 i 到 j 成为回文字符需要添加的最少字符数量13         for (int j=1;j
     
      =0;i--) {    //由内向外扩散15                 if (s[i]==s[j]) {16                     if (i==j-1)    dp[i][j]=0;17                     else dp[i][j] = dp[i+1][j-1];18                 }else {19                     dp[i][j] = Math.min(dp[i][j-1], dp[i+1][j])+1;20                 }21             }22         }23         char res[] = new char[s.length+dp[0][s.length-1]];  //最终需要的长度24         int i=0;int left=0;25         int j=s.length-1; 26         int right=res.length-1;27         while(i<=j) {28             if (s[i]==s[j]) {29                 res[left++]=s[i++];30                 res[right--]=s[j--];31             }else {32                 if (dp[i][j-1]
     

 题目二：给定一个字符串，给该字符串删除一些字符，使其成为一个回文串，求需要删除的最少字符数，并求出删除字符后回文串的样子，如果有多个这样的回文串，只用返回其中一个即可

比如  str="A"   那么不用删除任何子串，就可形成回文“A”

         str="AB" 那么可以删除“A” ，就可以形成回文“B”

         str="ABAD"  那么可以删除“D” 就可以形成回文“ABA”

第二道题目虽然题目和第一题很像，但解法却不一样，可以采用倒转原字符串，形成新的字符串str2，然后再求str1与str2的最长公共子序列即可，求最长公共子序列需要开一个二维数组dp[i][j],表示str1的前 i个字符和str2的前 j个字符的最长

公共子序列，如果i 和 j 相等， 那么 dp[i][j] = dp[i-1][j-1]+1, 如果 i 和 j 不相等，那么取dp[i][j-1] 和 dp[i-1][j] 两个字串的长度中选一个最大的，具体代码如下：

1 import java.util.*; 2 /*给定字符串,删除最少成为回文字符串,采用动态规划*/ 3 public class Main { 4     public static void main(String[] args) { 5         Scanner scan = new Scanner(System.in); 6         String str = scan.nextLine(); 7         char s1[] = str.toCharArray(); 8         char s2[] = reverse(str.toCharArray()); 9         int dp[][] = new int [str.length()][str.length()];  // 记录最长子序列10         boolean flag=false;11         //对第0行单独处理12         for (int j=0;j
     
      dp[i][j-1]) {32                     dp[i][j] = dp[i-1][j];33                 }else {34                     dp[i][j]=dp[i][j-1];35                 }36             }37         }38         39         //反推最长子序列40         int len = dp[s1.length-1][s2.length-1];41         int i = s1.length-1;42         int j=s2.length-1;43         while(len>0) {44             if (i>=1&&dp[i][j]==dp[i-1][j]) {45                 i--;46             }else if (j>=1 && dp[i][j]==dp[i][j-1]) {47                 j--;48             }else {49                 System.out.print(s1[i]);   //与前面的不等，说明这是最长子序列里面的元素，输出50                 len--;51                 i--;52                 j--;53             }54         }55     }56     public static char[] reverse(char c[]) {57         int i=0;  58         int j=c.length-1;59         while(i