24算法刷题 | Day46 | 动态规划 XIII | 子序列问题 IV | LeetCode 647. 回文子串，516. 最长回文子序列
目录
- 647. 回文子串
- 题目描述
- 题解
- 516. 最长回文子序列
- 题目描述
- 题解
647. 回文子串
点此跳转题目链接
题目描述
给你一个字符串 s ，请你统计并返回这个字符串中 回文子串 的数目。
回文字符串 是正着读和倒过来读一样的字符串。
子字符串 是字符串中的由连续字符组成的一个序列。
示例 1：
输入：s = "abc"
输出：3
解释：三个回文子串: "a", "b", "c"
示例 2：
输入：s = "aaa"
输出：6
解释：6个回文子串: "a", "a", "a", "aa", "aa", "aaa"
提示：
1 <= s.length <= 1000s由小写英文字母组成
题解
动态规划 经典题型之一。
首先考虑暴力解法，不难看出需要 O ( n 2 ) O(n^2) O(n2) 的时间复杂度来遍历所有子串，然后对每个子串又需要花费 O ( n ) O(n) O(n) 的时间复杂度来判断它是不是回文的，所以总时间复杂度为 O ( n 3 ) O(n^3) O(n3) 。
于是考虑引入动态规划中经典的 dp 数组，简化循环遍历和判断回文的过程。考虑一个子串 s[i, j] ：
-
如果
i = j，即单个字符，视为回文子串 -
否则，即多个字符组成的子串，
-
如果
i + 1 = j，即两个字符组成的子串，显然它俩相同即构成回文子串、否则不构成 -
否则，即大于两个字符组成的子串，
-
如果
s[i] != s[j]，显然不构成回文子串 -
否则，取决于其内部的子串
s[i + 1, j - 1]是否回文，即：
可以看出，此时若
s[i + 1, j - 1]回文，则s[i, j]也回文。
-
-
综上所述， 我们可以
-
确定
dp数组含义：dp[i][j]表示子串s[i][j]是否回文这与常见的动态规划中
dp数组不太一样，因为这里的dp并不直接存储正确结果的数量，而是判断结果是否正确（本题中即是否回文）。所以为了记录正确结果数量，可以维护一个计数器
res，每次判断出dp[i][j] = true后res加一即可。 -
确定状态转移方程：根据上面的分析，不难得出
if (i == j) { dp[i][j] = true; res++; } else if (s[i] == s[j]) { if (i + 1 == j) { dp[i][j] = true; res++; } else { dp[i][j] = dp[i + 1][j - 1]; if (dp[i][j]) { res++; } } }将
dp数组初始化为全false，则不用单独处理s[i] != s[j]的情况了。 -
确定遍历顺序：根据状态转移方程，
dp[i][j]由dp[i + 1][j - 1]转移而来，而dp[i + 1][j - 1]是在dp[i][j]的 “左下角” ：
所以，遍历顺序要 “从下到上、从左到右” ，即：
for (int i = n; i >= 0; --i) { for (int j = i; j <= n; ++j) { ... } }
代码（C++）
class Solution {
public:
int countSubstrings(string s) {
// 初始化dp数组（全为false）
vector<vector<bool>> dp(s.size(), vector<bool>(s.size(), false));
int res = 0;
for (int i = s.size() - 1; i >= 0; --i) {
for (int j = i; j < s.size(); ++j) {
if (i == j) {
dp[i][j] = true;
res++;
} else if (s[i] == s[j]) {
if (i + 1 == j) {
dp[i][j] = true;
res++;
} else {
dp[i][j] = dp[i + 1][j - 1];
if (dp[i][j]) {
res++;
}
}
}
}
}
return res;
}
};
516. 最长回文子序列
点此跳转题目链接
题目描述
给你一个字符串 s ，找出其中最长的回文子序列，并返回该序列的长度。
子序列定义为：不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列。
示例 1：
输入：s = "bbbab"
输出：4
解释：一个可能的最长回文子序列为 "bbbb" 。
示例 2：
输入：s = "cbbd"
输出：2
解释：一个可能的最长回文子序列为 "bb" 。
提示：
1 <= s.length <= 1000s仅由小写英文字母组成
题解
动态规划 解决，如果做了前面的那些子序列类型题目，这题基本可以秒了：
-
确定
dp数组含义：dp[i][j]表示子串s[i][j]中最长回文子序列的长度 -
状态转移方程：
- 如果
i = j，即单个字符，视为回文子序列，长度为1 - 否则，
- 如果
s[i] = s[j]，相当于其内部的最长回文子序列有增加了相同的一头一尾，故dp[i][j] = dp[i + 1][j - 1] + 2 - 否则，尝试拿
s[i]或s[j]与内部的子串匹配，或许能增长最长回文子序列，即dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])
- 如果
- 如果
-
确定遍历顺序：从状态转移方程可以看出，
dp[i][j]可以从三种状态转移而来：dp[i + 1][j - 1]dp[i + 1][j]dp[i][j - 1]
相应的，遍历顺序自然应该是：
for (int i = s.size() - 1; i >= 0; --i) { for (int j = i; j < s.size(); ++j) { ... } }
代码
c++
class Solution {
public:
int longestPalindromeSubseq(string s) {
vector<vector<int>> dp(s.size(), vector<int>(s.size(), 0));
for (int i = s.size() - 1; i >= 0; --i) {
for (int j = i; j < s.size(); ++j) {
if (i == j) {
dp[i][j] = 1;
} else if (s[i] == s[j]) {
dp[i][j] = dp[i + 1][j - 1] + 2;
} else {
dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);
}
}
}
return dp[0][s.size() - 1];
}
};
python
class Solution:
def longestPalindromeSubseq(self, s: str) -> int:
dp = [[0 for _ in range(len(s))] for _ in range(len(s))]
for i in range(len(s) - 1, -1, -1):
for j in range(i, len(s)):
if i == j:
dp[i][j] = 1
elif s[i] == s[j]:
dp[i][j] = dp[i + 1][j - 1] + 2
else:
dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])
return dp[0][-1]
golang
func longestPalindromeSubseq(s string) int {
dp := make([][]int, len(s))
for i := range dp {
dp[i] = make([]int, len(s))
}
for i := len(s) - 1; i >= 0; i-- {
for j := i; j < len(s); j++ {
if i == j {
dp[i][j] = 1
} else if s[i] == s[j] {
dp[i][j] = dp[i+1][j-1] + 2
} else {
dp[i][j] = max(dp[i+1][j], dp[i][j-1])
}
}
}
return dp[0][len(s)-1]
}