动态规划——leetcode5、最长回文子串
1、题目描述：
2、解题方法：动态规划
动态规划解题步骤：
1、确定状态
-
-
- 最后一步：如果s[i,…,j]是回文子串，那么需要满足两个条件
-
① s[i] == s[j]；
② s[i+1,…,j-1]是回文子串；
-
-
- 子问题：我们要验证s[i+1,…,j-1]是不是回文子串
- 用dp[i][j]来表示s[i,…,j]是不是回文子串
-
2、转移方程
dp[i][j] = （s[i] == s[j]）&& dp[i+1][j-1]
3、初始条件和边界情况
初始条件：dp[i][i] == true;
边界条件：在s[i] == s[j]的条件下，j-i<=2或者j-i<3，即说明s[i,…,j]的长度为2或者是3时，不用检查是不是回文串。
4、计算顺序
以字符串s:babab为例，一列一列的进行填表，先升序填列，再升序填行。
3、代码：
public String longestPalindrome(String s) { int len = s.length(); if(len < 2){ return s; } int maxLen = 1; int start = 0; char[] res = s.toCharArray(); boolean[][] dp = new boolean[len][len]; for(int i = 0; i < len; i++){ dp[i][i] = true; } for(int j = 1; j < len; j++){ for(int i = 0; i < j; i++){ if(res[i] == res[j]){ if(j - i < 3 || dp[i+1][j-1] == true){ dp[i][j] = true; } if( j-i+1 > maxLen && dp[i][j] == true){ maxLen = j-i+1; start = i; } } } } return s.substring(start,start + maxLen); }
