目录
①力扣647. 回文子串
难度 中等
给你一个字符串 s ，请你统计并返回这个字符串中 回文子串 的数目。
回文字符串 是正着读和倒过来读一样的字符串。
子字符串 是字符串中的由连续字符组成的一个序列。
具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。
示例 1：
输入：s = "abc" 输出：3 解释：三个回文子串: "a", "b", "c"
示例 2：
输入：s = "aaa" 输出：6 解释：6个回文子串: "a", "a", "a", "aa", "aa", "aaa"
提示：
1 <= s.length <= 1000s由小写英文字母组成
class Solution {
public:
int countSubstrings(string s) {
}
};解析代码
这道题虽然动态规划的解法不是最优的解法（官方题解的中心拓展解法简单且空间是O（1），两种解法的时间都是O（N^2），但此题动态规划解法空间是O（N^2）），但是可以为后面的回文串dp类型的困难题做准备，思路就是可以先预处理一下，将所有子串是否回文的信息统计在 dp 表里面，然后直接在表里面统计 true 的个数即可。
状态表示： 为了能表示出来所有的子串，我们可以创建⼀个 n * n 的二维 dp 表，只用到上三角部分即可。 其中， dp[i][j] 表示： s 字符串区间 [i, j] 的子串，是否是回文串。
状态转移方程：对于回文串，我们一般分析一个区间两头的元素：
当 s[i] != s[j] 的时候：不可能是回文串， dp[i][j] = 0 ;
当 s[i] == s[j] 的时候：根据长度分三种情况讨论：
- 长度为 1 ，也就是 i == j ：此时一定是回文串， dp[i][j] = true ;
- 长度为 2 ，也就是 i + 1 == j ：此时也一定是回文串， dp[i][j] = true ;
- 长度大于 2 ，此时要去看看 [i + 1, j - 1] 区间的子串是否回文： dp[i][j]= dp[i + 1][j - 1] ;
综上，状态转移方程分情况谈论即可。
分情况很细，无需初始化，填 j 用到 j - 1，所以从下往上填表，最后返回dp表中ture的个数。
class Solution {
public:
int countSubstrings(string s) {
int n = s.size(), ret = 0;
vector<vector<bool>> dp(n, vector<bool>(n, false));
// dp[i][j] 表示： s 字符串区间 [i, j] 的子串，是否是回文串
for(int i = n - 1; i >= 0; --i)
{
for(int j = i; j < n; ++j)
{
if(s[i] == s[j])
// if(i == j || i + 1 == j)
dp[i][j] = i + 1 >= j ? true : dp[i + 1][j - 1] ;
if(dp[i][j])
++ret;
}
}
return ret;
}
};②力扣5. 最长回文子串
难度 中等
给你一个字符串 s，找到 s 中最长的回文子串。
如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。
示例 1：
输入：s = "babad" 输出："bab" 解释："aba" 同样是符合题意的答案。
示例 2：
输入：s = "cbbd" 输出："bb"
提示：
1 <= s.length <= 1000s仅由数字和英文字母组成
class Solution {
public:
string longestPalindrome(string s) {
}
};解析代码
先用 dp 表统计出所有子串是否回文的信息 b，然后根据 dp 表示 true 的位置，得到回文串的起始位置和长度。 那么我们就可以在表中找出最长回文串。 关于预处理所有子串是否回文，已经在力扣647. 回文子串讲过，
class Solution {
public:
string longestPalindrome(string s) {
int n = s.size(), maxLen = 1, begin = 0;
string ret = "";
vector<vector<bool>> dp(n, vector<bool>(n, false));
// dp[i][j] 表示： s 字符串区间 [i, j] 的子串，是否是回文串
for(int i = n - 1; i >= 0; --i)
{
for(int j = i; j < n; ++j)
{
if(s[i] == s[j])
// if(i == j || i + 1 == j)
dp[i][j] = i + 1 >= j ? true : dp[i + 1][j - 1] ;
if(dp[i][j] && maxLen < j - i + 1)
maxLen = j - i + 1, begin = i;
}
}
return s.substr(begin, maxLen);
}
};③力扣1745. 分割回文串 IV
难度 困难
给你一个字符串 s ，如果可以将它分割成三个 非空 回文子字符串，那么返回 true ，否则返回 false 。
当一个字符串正着读和反着读是一模一样的，就称其为 回文字符串 。
示例 1：
输入：s = "abcbdd" 输出：true 解释："abcbdd" = "a" + "bcb" + "dd"，三个子字符串都是回文的。
示例 2：
输入：s = "bcbddxy" 输出：false 解释：s 没办法被分割成 3 个回文子字符串。
提示：
3 <= s.length <= 2000s 只包含小写英文字母。
class Solution {
public:
bool checkPartitioning(string s) {
}
};解析代码
题目要求⼀个字符串被分成三个非空回文子串，一看要表示的状态很多，有些无从下手。 其实可以把它拆成两个小问题：
- 动态规划求解字符串中的一段非空子串是否是回文串。
- 枚举三个子串除字符串端点外的起止点，查询这三段非空子串是否是回文串。
那么这道困难题就变为简单题了，变成了一道枚举题。 关于预处理所有子串是否回文，已经在力扣647. 回文子串讲过。
class Solution {
public:
bool checkPartitioning(string s) {
int n = s.size();
vector<vector<bool>> dp(n, vector<bool>(n, false));
for(int i = n - 1; i >= 0; --i)
{
for(int j = i; j < n; ++j)
{
if(s[i] == s[j])
dp[i][j] = i + 1 >= j ? true : dp[i+1][j-1];
}
}
for(int i = 1; i < n - 1; ++i) // 枚举第二个字符串的开头和结尾
{
for(int j = i; j < n - 1; ++j)
{
if(dp[0][i - 1] && dp[i][j] && dp[j + 1][n - 1])
return true;
}
}
return false;
}
};④力扣132. 分割回文串 II
给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是回文串。
返回符合要求的 最少分割次数 。
示例 1：
输入：s = "aab" 输出：1 解释：只需一次分割就可将 s 分割成 ["aa","b"] 这样两个回文子串。
示例 2：
输入：s = "a" 输出：0
示例 3：
输入：s = "ab" 输出：1
提示：
1 <= s.length <= 2000s仅由小写英文字母组成
class Solution {
public:
int minCut(string s) {
}
};解析代码
用 i 位置为结尾定义状态表：dp[i] 表示： s 中 [0, i] 区间上的字符串，最少分割的次数。
状态转移方程：根据最后一个位置的信息来分析：设 0 <= j <= i ，那么我们可以 根据 j ~ i 位置上的子串是否是回文串分成下面两类：
- 当 [j ,i] 位置上的子串能够构成一个回文串，那么 dp[i] 就等于 [0, j - 1] 区 间上最少回文串的个数 + 1，即 dp[i] = dp[j - 1] + 1 ;
- 当 [j ,i] 位置上的子串不能构成一个回文串，此时 j 位置就不用考虑。
由于我们要的是最小值，因此应该循环遍历一遍 j 的取值，拿到里面的最小值即可。dp[i] = min(dp[i], dp[j - 1] + 1);
优化：我们在状态转移方程里面分析到，要能够快速判读字符串里面的子串是否回文。因此可以先预处理⼀个 dp 表，里面保存所有子串是否回文的信息。关于预处理所有子串是否回文，已经在力扣647. 回文子串讲过。
初始化、填表顺序、返回值：
观察状态转移方程，会用到 j - 1 位置的值。可以思考一下当 j == 0 的时候， 表示的区间就是 [0, i] 。如果 [0, i] 区间上的字符串已经是回文串了，最小的回文串就是 1 了， j 往后的值就不用遍历了。 因此可以在循环遍历 j 的值之前处理 j == 0 的情况，然后 j 从 1 开始循环。 但是，为了防止求 min 操作时， 0 干扰结果。要先把表里面的值初始化为无穷大。
从左往右填表，最后返回dp[i - 1]。
class Solution {
public:
int minCut(string s) {
int n = s.size();
vector<vector<bool>> isPal(n, vector<bool>(n, false));
// isPal[i][j] 表示： s 字符串区间 [i, j] 的子串，是否是回文串Palindrome string
for(int i = n - 1; i >= 0; --i)
{
for(int j = i; j < n; ++j)
{
if(s[i] == s[j])
isPal[i][j] = i + 1 >= j ? true : isPal[i+1][j-1];
}
}
vector<int> dp(n, INT_MAX);
// dp[i] 表示： s 中 [0, i] 区间上的字符串，最少分割的次数
for(int i = 0; i < n; ++i)
{
if(isPal[0][i])
{
dp[i] = 0;
}
else
{
for(int j = 1; j <= i; ++j)
{
if(isPal[j][i]) // 注意是j i
dp[i] = min(dp[i], dp[j - 1] + 1);
}
}
}
return dp[n - 1];
}
};⑤力扣516. 最长回文子序列
难度 中等
给你一个字符串 s ，找出其中最长的回文子序列，并返回该序列的长度。
子序列定义为：不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列。
示例 1：
输入：s = "bbbab" 输出：4 解释：一个可能的最长回文子序列为 "bbbb" 。
示例 2：
输入：s = "cbbd" 输出：2 解释：一个可能的最长回文子序列为 "bb" 。
提示：
1 <= s.length <= 1000s仅由小写英文字母组成
class Solution {
public:
int longestPalindromeSubseq(string s) {
}
};解析代码
状态表示：
关于单个字符串问题中的回文子序列，或者回文子串，我们的状态表示研究的对象一般都是选取原字符串中的用段区域 [i, j] 内部的情况。这里继续选取字符串中的一段区域来研究：
dp[i][j] 表示：s 字符串 [i, j] 区间内的所有的子序列中，最长的回文子序列的长度
状态转移方程： 关于回文子序列和回文子串的分析方式，一般都是比较固定的，都是选择这段区域的左右端点的字符情况来分析。因为如果一个序列是回文串的话，去掉首尾两个元素之后依旧是回文串，首尾加上两个相同的元素之后也依旧是回文串。因为，根据首尾元素的不同，可以分为下面两种情况：
- 当首尾两个元素相同的时候，也就是 s[i] == s[j] ：那么 [i, j] 区间上的最长回文子序列，应该是 [i + 1, j - 1] 区间内的那个最长回文子序列首尾填上 s[i] 和 s[j] ，此时dp[i][j] = dp[i + 1][j - 1] + 2
- 当首尾两个元素不相同的时候，也就是 s[i] != s[j] ：此时这两个元素就不能同时添加在一个回⽂串的左右，那么我们就应该让 s[i] 单独加在⼀个序列的左边，或者让 s[j] 单独放在⼀个序列的右边，看看这两种情况下的最大值：
单独加入 s[i] 后的区间在 [i, j - 1] ，此时最长的回文序列的长度就是 dp[i][j - 1] ；
单独加入 s[j] 后的区间在 [i + 1, j] ，此时最长的回文序列的长度就是 dp[i+ 1][j] ；
取两者的最大值，于是 dp[i][j] = max(dp[i][j - 1], dp[i + 1][j]) ;
综上所述，状态转移方程为：
- 当 s[i] == s[j] 时： dp[i][j] = dp[i + 1][j - 1] + 2 ;
- 当 s[i] != s[j] 时： dp[i][j] = max(dp[i][j - 1], dp[i + 1][j]) ;
初始化、填表顺序、返回值：
根据状态转移方程 dp[i][j] = dp[i + 1][j - 1] + 2 ，状态表示的时候，选取的是⼀段区间，因此需要要求左端点的值要小于等于右端点的值，因此会有两种边界情况：
- 当 i == j 的时候， i + 1 就会大于 j - 1 ，此时区间内只有一个字符。这个比较好分析， dp[i][j] 表示一个字符的最长回文序列，一个字符能够自己组成回文串，因此此时 dp[i][j] = 1 ;
- 当 i + 1 == j 的时候， i + 1 也会大于 j - 1 ，此时区间内有两个字符。这样也好分析，当这两个字符相同的时候， dp[i][j] = 2 ; 不相同的时候， d[i][j] = 0 ;
对于第一种边界情况，在填表的时候就可以同步处理。 对于第二种边界情况， dp[i + 1][j -1] 的值为 0 ，不会影响最终的结果，因此可以不用考虑。
dp[i + 1] 表示下一行的位置， dp[j - 1] 表示前一列的位置，所以从下往上填表，返回dp[0][n - 1];
class Solution {
public:
int longestPalindromeSubseq(string s) {
int n = s.size();
vector<vector<int>> dp(n, vector<int>(n));
// dp[i][j] 表示：s 字符串 [i, j]区间内的所有的子序列中，最长的回文子序列的长度
for(int i = n - 1; i >= 0; --i) // 枚举左端点i
{
dp[i][i] = 1; // i等于j的情况
for(int j = i + 1; j < n; ++j) // 枚举右端点j
{
if(s[i] == s[j]) // dp[i + 1][j - 1] 无效就是0
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][n - 1];
}
};⑥力扣1312. 让字符串成为回文串的最少插入次数
难度 困难
给你一个字符串 s ，每一次操作你都可以在字符串的任意位置插入任意字符。
请你返回让 s 成为回文串的 最少操作次数 。
「回文串」是正读和反读都相同的字符串。
示例 1：
输入：s = "zzazz" 输出：0 解释：字符串 "zzazz" 已经是回文串了，所以不需要做任何插入操作。
示例 2：
输入：s = "mbadm" 输出：2 解释：字符串可变为 "mbdadbm" 或者 "mdbabdm" 。
示例 3：
输入：s = "leetcode" 输出：5 解释：插入 5 个字符后字符串变为 "leetcodocteel" 。
提示：
1 <= s.length <= 500s中所有字符都是小写字母。
class Solution {
public:
int minInsertions(string s) {
}
};解析代码
状态表示：
关于单个字符串问题中的回文子序列，或者回文子串，状态表示研究的对象一般都是选取原字符串中的⼀段区域 [i, j] 内部的情况。这里继续选取字符串中的⼀段区域 来研究： 状态表示： dp[i][j] 表是字符串 [i, j] 区域成为回文子串的最少插入次数。
状态转移方程：
关于回文子序列和回文子串的分析方式，一般都是比较固定的，都是选择这段区域的左右端点的字符情况来分析。因为如果⼀个序列是回文串的话，去掉首尾两个元素之后依旧是回文串，首尾加上两个相同的元素之后也依旧是回文串」。因为，根据首尾元素的不同，可以分为下面两种情况：
- 当首尾两个元素「相同」的时候，也就是 s[i] == s[j] ：
- 那么 [i, j] 区间内成为回文子串的最少插入次数，取决于 [i + 1, j - 1] 区间内成为回文子串的最少插⼊次数；
- 若 i == j 或 i == j - 1 （ [i + 1, j - 1] 不构成合法区间），此时只有 1~ 2 个相同的字符， [i, j] 区间⼀定是回文子串，成为回文子串的最少插入次数是0。 此时 dp[i][j] = i>= j - 1 ? 0 : dp[i + 1][j - 1] ；
- 当是尾两个元素不相同的时候，也就是 s[i] != s[j] ：
- 此时可以在区间最右边补上⼀个 s[i] ，需要的最少插⼊次数是 [i + 1, j] 成为回文子串的最少插入次数 + 本次插入，即 dp[i][j] = dp[i + 1][j] + 1 ；
- 或者在区间最左边补上⼀个 s[j] ，需要的最少插⼊次数是 [i, j + 1] 成为回文子串的最少插入次数 + 本次插入，即 dp[i][j] = dp[i][j + 1] + 1 ；
综上所述，状态转移方程为：
- 当 s[i] == s[j] 时： dp[i][j] = i >= j - 1 ? 0 : dp[i + 1][j - 1] ;
- 当 s[i] != s[j] 时： dp[i][j] = min(dp[i + 1][j], dp[i][j - 1]) + 1 ;
初始化：根据状态转移方程，初始化成0，第一条状态转移方程就不用判断了。
填表顺序：根据状态转移发现，在 dp 表所表示的矩阵中， dp[i + 1] 表⽰下一行的位置， dp[j - 1] 表示前⼀列的位置。因此填表顺序应该是从下往上填写每一行，每一行从左往右。
返回值：根据状态表示，需要返回 [0, n -1] 区域上成为回文子串的最少插入次数，因此需要返回 dp[0][n - 1] 。
class Solution {
public:
int minInsertions(string s) {
int n = s.size();
vector<vector<int>> dp(n, vector<int>(n, 0));
// dp[i][j] 表是字符串 [i, j] 区域成为回文子串的最少插入次数
for(int i = n - 1; i >= 0; --i)
{
for(int j = i + 1; j < n; ++j)
{
if(s[i] == s[j])
dp[i][j] = dp[i + 1][j - 1];
else
dp[i][j] = min(dp[i + 1][j], dp[i][j - 1]) + 1;
}
}
return dp[0][n - 1];
}
};
本篇完。
下一篇首优先级队列_堆相关的OJ。
下下篇动态规划类型的是两个数组dp类型的OJ。
标签：子串,21,Offer,int,由易到难,序列,字符串,dp,回文 From： https://blog.csdn.net/GRrtx/article/details/136620740