代码随想录算法训练营第五十七天 647. 回文子串、516.最长回文子序列、动态规划章节总结

本文主要是介绍代码随想录算法训练营第五十七天 647. 回文子串、516.最长回文子序列、动态规划章节总结，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

代码随想录算法训练营第五十七天 | 647. 回文子串、516.最长回文子序列、动态规划章节总结

647. 回文子串

题目链接：647. 回文子串 - 力扣（LeetCode）

// dp法
class Solution {public int countSubstrings(String s) {int len = s.length();int count = 0;/**当s[i] != s[j]时，那没啥好说的了，dp[i][j]一定是false。当s[i] == s[j]时，这就复杂一些了，有如下三种情况情况一：下标i 与 j相同，同一个字符例如a，当然是回文子串情况二：下标i 与 j相差为1，例如aa，也是回文子串情况三：下标：i 与 j相差大于1的时候，例如cabac，此时s[i]与s[j]已经相同了，我们看i到j区间是不是回文子串就看aba是不是回文就可以了，那么aba的区间就是 i+1 与 j-1区间，这个区间是不是回文就看dp[i + 1][j - 1]是否为true*/// dp[i][j] 表示子字符串（下表范围[i, j]）） 是否是回文boolean[][] dp = new boolean[len][len];// 初始化 ：dp[i][j] 全部初始化为falsefor(int i = len - 1; i >= 0; --i) {for(int j = i; j < len; ++j) {// 只有在这种情况下，才能if(s.charAt(i) == s.charAt(j)) { // 情况一 和 情况二if(j - i <= 1) {dp[i][j] = true;count++;// 情况三} else if (dp[i+1][j-1]) {dp[i][j] = true;count++;}}}}return count;}
}// 双指针法
}class Solution {public int countSubstrings(String s) {int len, ans = 0;if (s == null || (len = s.length()) < 1) return 0;for(int i = 0; i < len; ++i) {ans += extend(s, i, i, len); // 以i为中心点ans += extend(s, i, i+1, len); // 以i和i+1为中心点}return ans;}int extend(String s, int i, int j, int n) {int res = 0;while (i >= 0 && j < n && s.charAt(i) == s.charAt(j)) {i--;j++;res++;}return res;}
}

516.最长回文子序列

题目链接：516. 最长回文子序列 - 力扣（LeetCode）

class Solution {public int longestPalindromeSubseq(String s) {int len = s.length();// dp[i][j] 表示 [i, j] 范围中最长的回文子序列长度int[][] dp = new int[len][len];for(int i = len - 1; i >= 0; --i) {dp[i][i] = 1; // 初始化for(int j = i + 1; j < len; ++j) {if(s.charAt(i) == s.charAt(j)) {dp[i][j] = dp[i+1][j-1] + 2; // 相等时，可以使[i+1,j-1]内最长回文子序列的长度+2} else {dp[i][j] = Math.max(dp[i+1][j], dp[i][j-1]); // 不相等，则只能在[i+1, j]和[i, j-1]中选一个最长的回文子序列长度}}}return dp[0][len - 1];}
}