动态规划实现回文字符串问题

问题⼀：求⼀个字符串的最⼤回⽂字符串长度;

　　1）思路：动态规划;

　　2）具体描述：设⽴⼀个长度len为字符串str，⽤⼀个dp[len][len]的⼆维数组来表⽰字符串i-j下标所构成的⼦串的长度，经过循环计算之后我们返回最⼤回⽂⼦串的长度即可，即返回dp[0][len-1];

　　3）dp数组的具体实现：根据动态规划⾃底向上的思想，从回⽂⼦串到求出整个最长回⽂字符串，⾸先从str的结尾开始遍历到str 的头部，同时每⼀次记录dp的初始值；如果str[i]==str[j],说明i-j为回⽂字符串，此时应该更新dp[i][j]的值；如果str[i]≠str[j]，应该判断dp[i+1][j]和dp[i][j-1]的⼤⼩，取出其中max作为最⼤长度更新dp[i][j]的值　　4）代码实现

1 static int longestPalindrome1(String str) { 2 int len = str.length();

3 for (int i = len - 1; i >= 0; i--) { 4 dp[i][i] = 1;

5 for (int j = i+1; j < len; j++) {

6 if(str.charAt(i) == str.charAt(j)) { 7 dp[i][j] = dp[i + 1][j - 1] +2; 8 } else {

9 dp[i][j] = Math.max(dp[i+1][j], dp[i][j-1]);10 }11 }12 }

13 return dp[0][len-1];14 }

　　5）测试结果：测试字符串12ABCBDABADBCBA34的最⼤回⽂串，我们可以看出最⼤回⽂串为ABCBDABADBCBAB，长度为13　　

问题⼆：将上述问题修改为输出最长回⽂⼦串

　　1）我们知道，动态规划最优解的⼦问题同样也是最优解，即最长回⽂字符串的⼦串也是回⽂串，假设p[i][j]是回⽂字符串，那么p[i+1][j-1]也是回⽂字符串，这样最长回⽂字符串就能够分解成为⼀系列⼦问题来求解。　　2）代码实现

1 static String longestPalindrome2(String str) { 2 int len = str.length();

3 int maxlen = 0, start = 0;

4 for (int i = 0; i < str.length(); i++) { 5 dp[i][i] = 1;

6 if(i < len -1 && str.charAt(i) == str.charAt(i+1)) { 7 dp[i][i+1] = 1; 8 start = i; 9 maxlen = 2;10 }11 }12

13 for (int i = 3; i < str.length(); i++) { //分析整个串长度14 for (int j = 0; j < len - i; j++) { //⼦串其实地址15 int m = i+j - 1; //⼦串结束地址

16 if(dp[j+1][i-1] == 1 && str.charAt(i) == str.charAt(j)) {17 dp[j][i] = 1;18 maxlen = i;19 start = j;20 }21 }22 }

23 return str.substring(start,start+maxlen-1);24 }

　　2）测试输⼊：同样是将上述测试⽤例，测试字符串12ABCBDABADBCBA34的最⼤回⽂串，我们可以看出最⼤回⽂串为ABCBDABADBCBAB