1. 回文子串?

647. 回文子串 - 力扣（LeetCode）

一個子串左右兩個元素相等，并且中間對稱，才是回文子串

即 i=j 時，[i+1: j-1]對稱

dp[i][j]：?[i:j] 是否是回文字串

當(dāng) 子串長度大于2 由 dp[i+1][j-1] 推出， i 由 i+1推出 所以 i 要倒序

不大于2時，則由 i j 決定

class Solution {public int countSubstrings(String s) {int length = s.length();boolean dp[][] = new boolean[length][length];// dp[i][j] [i:j] 是否是回文字串int res = 0;for(int i = length-1; i > -1; i--){for(int j = i; j < length; j++){if(s.charAt(i) == s.charAt(j)){if(j-i <= 1){ // 字串長度不超過2dp[i][j] = true;res++;}else if(dp[i+1][j-1]){dp[i][j] = true;res++;}}}}return res;}
}

?

2. 最長回文子序列

516. 最長回文子序列 - 力扣（LeetCode）

子序列可以不連續(xù) 所以當(dāng) s[i] != s[j] 也需要考慮

s[i] == s[j] 時，中間的長度 + 2

s[i] != s[j] 時，要考慮左右兩個哪個加入中間后更長

class Solution {public int longestPalindromeSubseq(String s) {int length = s.length();int[][] dp = new int[length][length];for(int i = length-1; i > -1; i--){dp[i][i] = 1; // 字串長度為 1 必然相等for(int j = i + 1; j < length; j++){if(s.charAt(i) == s.charAt(j)){dp[i][j] = dp[i+1][j-1] + 2; // dp[1][2] = dp[2][1] + 2 = 0 + 2}else{dp[i][j] = Math.max(dp[i+1][j], dp[i][j-1]);}}}return dp[0][length-1];}
}