动态规划 | part13

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[i+1][j-1]的结果。
  • 只有当i从大到小遍历时，计算dp[i][j]时，dp[i+1][...]的结果才已经被计算并存储好了。如果i从小到大遍历，依赖的数据还没算出来，逻辑就会出错

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

给定一个字符串 s ，找到其中最长的回文子序列，并返回该序列的长度。可以假设 s 的最大长度为 1000 。

示例 1: 输入: "bbbab" 输出: 4 一个可能的最长回文子序列为 "bbbb"。

示例 2: 输入:"cbbd" 输出: 2 一个可能的最长回文子序列为 "bb"。

提示：

• 1 <= s.length <= 1000
• s 只包含小写英文字母

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]（或者都不包含，但这被前两种情况覆盖了）