版权声明：本文为博主原创文章，未经博主允许不得转载。 https://blog.csdn.net/sinat_32502811/article/details/81563189
最近在刷题，对于动态规划类的问题完全懵逼····就从LeetCode上找DP的题目专门练习一下，熟悉熟悉思路。
这里还有一个动态规划背包问题的比较好的资源，请戳这里.
LeetCode05
Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.
Example 1:
Input: “babad”
Output: “bab”
Note: “aba” is also a valid answer.
貌似字符串问题中，有好多都是动态规划类问题，比如经典的最大相同子串，以及这道最长回文子串。
最开始，我想到的思路是：类似最大相同子串的方法，对于二维数组dp[i][j]，i用字符串的正序，j用字符串的倒序，如果str[i] == str[j] 并且dp[i - 1] [j - 1] 不为0的话，则最长回文子串长度就是dp[i-1]+dp[j-1],对于题目提供的样例，这个方法做出来是对的，但是在测评的时候，有一个样例，“abcefcba”就不对。
所以这种思路被抛弃。
结合在discussion部分看到别人的代码，思路是这样的。dp数组为boolean类型，代表从i 到 j位置的字符串是否为回文。如果从 j 到 i 为回文子串，那么它的子问题就是str[i]==str[j]并且由j+1 到 i- 1也是回文子串。因此状态转移方程就为：
dp[i][j]=⎧⎩⎨⎪⎪truetruefalse,ifdp[j+1][i−1]=trueandstr[i]==str[j],i−j<=2andstr[i]==str[j],elsedp[i][j]={true,ifdp[j+1][i−1]=trueandstr[i]==str[j]true,i−j<=2andstr[i]==str[j]false,else
代码如下：
class Solution {
public String longestPalindrome(String s) {
int len = s.length();
boolean[][] dp = new boolean[len][len];
int max = 0;
int start = 0;
int end = 0;
for(int i = 0; i < len; i++){
for(int j = 0; j <= i; j++){
if(s.charAt(i) == s.charAt(j) && (i - j <= 2 || dp[j+1][i - 1])){
dp[j][i] = true;
}
if(dp[j][i] && max < (i - j + 1)){
max = i - j + 1;
start = j;
end = i+1;
}
}
}
return s.substring(start, end);
}
}
