動態規劃——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); }
