代码随想录训练营 Day57

今日任务

647.回文子串
516.最长回文子序列
动态规划总结
语言：Java

647. 回文子串

链接：https://leetcode.cn/problems/palindromic-substrings/

class Solution {public int countSubstrings(String s) {int[][] dp = new int[s.length()][s.length()];//dp[i][j]: 从i~j的子串是否为回文子串int res = 0;for(int i = s.length() - 1; i >= 0; i--){for(int j = i; j < s.length(); j++){if(s.charAt(i) == s.charAt(j)){if(i == j){dp[i][j] = 1;}else if(Math.abs(j - i) == 1){dp[i][j] = 1;}else if(j - i > 1){dp[i][j] = dp[i + 1][j - 1];}}res += dp[i][j];}}return res;}
};/*a   b   b   a   ca   1   0   0   1   0b       1   1   0   0b           1   0   0a               1   0c                   1*/

516. 最长回文子序列

链接：https://leetcode.cn/problems/longest-palindromic-subsequence/
代码随想录

class Solution {public int longestPalindromeSubseq(String s) {int[][] dp = new int[s.length()][s.length()];//i~j位的最长子串长度for(int i = 0; i < s.length(); i++){dp[i][i] = 1;}for(int i = s.length() - 1; i >= 0; i--){for(int j = i + 1; j < s.length(); j++){//如果相等，就说明i位和j位都可以加入到当前最长回文子序列中if(s.charAt(i) == s.charAt(j)){dp[i][j] = dp[i + 1][j - 1] + 2;}//如果不相等，就寻找加入i位或j位后最长回文子序列更长的else{dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);}}}return dp[0][s.length() - 1];}
}
/*b   b   b   a   bb   1   2   3   3   4b       1   2   2   3b           1   1   2a               1   1b                   1*/
/*c   b   b   dc   1   1   2   2b       1   2   2b           1   1d               1*/