代码随想录day40：动态规划part13

 647. 回文子串

class Solution {public int countSubstrings(String s) {char[] chars = s.toCharArray();int len = chars.length;boolean [][] dp = new boolean[len][len];int result = 0;for(int i = len - 1; i >= 0; i--){for(int j = i; j < len; j++){if(chars[i] == chars[j]){if (j - i <= 1) { // 情况一 和 情况二result++;dp[i][j] = true;} else if (dp[i + 1][j - 1]) { //情况三result++;dp[i][j] = true;}}}}return result;}
}

516. 最长回文子序列

class Solution {public int longestPalindromeSubseq(String s) {int n = s.length();int[][] dp = new int[n][n];for(int i = n -1; i >= 0; i--){dp[i][i] = 1;for(int j = i + 1; j < n; j ++){if(s.charAt(i) == s.charAt(j)){dp[i][j] = dp[i + 1][j - 1] + 2;}else{dp[i][j] = Math.max(dp[i + 1][j],dp[i][j - 1]);}}}return dp[0][n - 1];}
}