647. 回文子串 - 力扣LeetCode给定一个字符串你的任务是计算这个字符串中有多少个回文子串。具有不同开始位置或结束位置的子串即使是由相同的字符组成也会被视作不同的子串。示例 1输入abc输出3解释三个回文子串: a, b, c示例 2输入aaa输出6解释6个回文子串: a, a, a, aa, aa, aaa提示输入的字符串长度不会超过 1000 。public int countSubstrings(String s) { // dp数组表示的是[i,j]是否为回文串 boolean[][] dp new boolean[s.length()][s.length()]; 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 (j - i 1) { dp[i][j] true; res; } else if (dp[i 1][j - 1]) { dp[i][j] true; res; } } else { dp[i][j] false; } } } return res; }解题dp[i][j]表示字符串s中从索引i到索引j的子串即s[i...j]是否是回文串。我们的循环顺序非常关键外层循环i从字符串的最后一个字符向前遍历到第一个字符倒序。内层循环j从当前i的位置向后遍历到字符串末尾。为什么要倒序遍历i因为判断dp[i][j]是否回文时依赖于内部子串dp[i1][j-1]的结果。只有当i从大到小遍历时计算dp[i][j]时dp[i1][...]的结果才已经被计算并存储好了。如果i从小到大遍历依赖的数据还没算出来逻辑就会出错516. 最长回文子序列 - 力扣LeetCode给定一个字符串 s 找到其中最长的回文子序列并返回该序列的长度。可以假设 s 的最大长度为 1000 。示例 1: 输入: bbbab 输出: 4 一个可能的最长回文子序列为 bbbb。示例 2: 输入:cbbd 输出: 2 一个可能的最长回文子序列为 bb。提示1 s.length 1000s 只包含小写英文字母public int longestPalindromeSubseq(String s) { // dp数组表示的是[i,j]的最长回文子串的长度 int[][] dp new int[s.length()][s.length()]; for (int i s.length() - 1; i 0; i--) { dp[i][i] 1; for (int j i 1; j s.length(); 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][s.length() - 1]; }解题子序列定义为不改变剩余字符顺序的情况下删除某些字符或者不删除任何字符形成的一个序列。这里的遍历顺序与上一题类似因为我们的状态是由前面左下角以及下方数据递推得到的所以我们需要从下往上从左往右进行遍历当我们匹配上的时候需要dp[i 1][j - 1] 2因为是一次俩个字符我们统计的是长度所以需要加2.如果不匹配的情况我们则需要考虑如果不考虑i以及不考虑j二者哪个的长度更大一些。既然两头不一样它们不可能同时出现在同一个回文子序列的两端。因此最长回文子序列要么不包含s[i]要么不包含s[j]或者都不包含但这被前两种情况覆盖了