Longest Palindromic Substring最长回文子串-学习动态规划Dynamic Programming(DP)

通过leetcode的查找Longest Palindromic Substring最长回文子串，来学习一下动态规划。
动态规划的核心是能把当前问题分解成已经有的更小的问题，然后直到这个问题有一个常数答案，并且这个分解过程有一个固定模式。

所以最终目的就是寻找 1. 固定的分解模式 2.常数答案。

根据回文串的定义可知，去掉回文串的首位，剩下的依然是回文串，重复这个过程，我们可以得到最终只有长度为1（奇数长度）或者0（偶数长度）的字符串，也就是一个常量解。
因此我们就得到了

1. 固定的分解模式，及回文串去掉首尾依然是回文串，翻过来，回文串加上相同的首尾依然是回文串。
2. 常数答案，2.1 一个字符是回文串， 2.2 两个相邻字符如果相同是回文串

假设 s为字符串，i和j表示索引，dp[i][j]=tue/false 分别表示字符串s[i...j]是/否为回文
则 dp[i][j]=dp[i+1][j-1] && s[i]==s[j]，及当s[i+1...j-1]是回文且s[i]=s[j]时，那么s[i...j]也是回文，及dp[i][j]=true;
因此可以得到转换方程

if (s.charAt(i) == s.charAt(j)) {       if (j - i <= 2) { //j=i||j=i+1          dp[i][j] = true;       } else {          dp[i][j] = dp[i + 1][j - 1];       } } else {       dp[i][j] = false; } 

实践中有两种写法，一种是从尾向前计算，好处是当在 (i,j) 时，(i+1,j-1) 一定已经被计算，另外一种是从头向后计算，好处是比较直观。

从尾向前:

public String longestPalindrome(String s) {         int n = s.length();         if (n < 2) {             return s;         }         int maxLen = 0;         int maxIndex = 0;         boolean[][] dp = new boolean[n][n];          for (int i = n - 1; i >= 0; i--) {             for (int j = i; j < n; j++) {                 if (s.charAt(i) == s.charAt(j)) {                     if (j - i <= 2) {                         dp[i][j] = true;                     } else {                         dp[i][j] = dp[i + 1][j - 1];                     }                     if (dp[i][j] && (j - i + 1 > maxLen)) {                         maxLen = j - i + 1;                         maxIndex = i;                     }                 } else {                     dp[i][j] = false;                 }             }         }         return s.substring(maxIndex, maxIndex + maxLen);     } 

从头向后

public String longestPalindrome(String s) {         int n = s.length();         if (n < 2) {             return s;         }         int maxLen = 0;         int maxIndex = 0;         boolean[][] dp = new boolean[n][n];          for (int len = 1; len <= n; len++) {             for (int i = 0; i + len - 1 < n; i++) {                 int j = i + len - 1;                 if (s.charAt(i) == s.charAt(j)) {                     if (j - i <= 2) {                         dp[i][j] = true;                     } else {                         dp[i][j] = dp[i + 1][j - 1];                     }                     if (dp[i][j] && (j - i + 1 > maxLen)) {                         maxLen = j - i + 1;                         maxIndex = i;                     }                 } else {                     dp[i][j] = false;                 }             }         }         return s.substring(maxIndex, maxIndex + maxLen);     }