
定义 dp[i][j] 表示 [i, j] 区间内的字符串是否是回文子串,i <= j,要特别注意填表顺序。

class Solution {
public:
int countSubstrings(string s) {
int n = s.size();
vector<vector<bool>> dp(n, vector<bool>(n));
int ret = 0;
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 ? dp[i + 1][j - 1] : true;
if (dp[i][j]) ret++;
}
}
return ret;
}
}; 一边填dp表,一边统计最长的回文子串。
class Solution {
public:
string longestPalindrome(string s) {
int n = s.size();
vector<vector<bool>> dp(n, vector<bool>(n));
int begin = 0, len = 1;
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 ? dp[i + 1][j - 1] : true;
if (dp[i][j] && j - i + 1 > len)
{
len = j - i + 1;
begin = i;
}
}
return s.substr(begin, len);
}
}; 
class Solution {
public:
bool checkPartitioning(string s) {
int n = s.size();
vector<vector<bool>> dp(n, vector<bool>(n));
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 ? dp[i + 1][j - 1] : true;
for (int i = 0; i < n - 1; i++)
for (int j = 0; j < n - 1; j++)
if (dp[0][i] && dp[i + 1][j] && dp[j + 1][n - 1])
return true;
return false;
}
};
定义状态 dp[i] 表示0-i区间符合要求的最少分割次数。

如果 j - i 是回文子串,则 dp[i] = dp[j - 1] + 1;后面的+1表示分割一次。
class Solution {
public:
int minCut(string s) {
int n = s.size();
vector<vector<bool>> isPal(n, vector<bool>(n));
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 ? isPal[i + 1][j - 1] : true;
vector<int> dp(n, INT_MAX);
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])
dp[i] = min(dp[j - 1] + 1, dp[i]);
}
}
return dp[n - 1];
}
};
定义状态 dp[i][j] 表示区间 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] 时: dp[i][j] = max(dp[i][j - 1], dp[i + 1][j])。

class Solution {
public:
int longestPalindromeSubseq(string s) {
int n = s.size();
vector<vector<int>> dp(n, vector<int>(n));
for (int i = n - 1; i >= 0; i--)
{
dp[i][i] = 1;
for (int j = i + 1; j < n; j++)
{
if (s[i] == s[j]) dp[i][j] = dp[i + 1][j - 1] + 2;
else dp[i][j] = max(dp[i][j - 1], dp[i + 1][j]);
}
}
return dp[0][n - 1];
}
};
定义状态 dp[i][j] 表示让i到j区间称为回文串的最小插入次数。

i == j 时不用考虑,在初始化dp表的时候其中的值默认为0,所以直接在 j = i + 1 处开始遍历;i + 1 == j 可以放在 i + 1 < j 中,因为 dp[i + 1][j - 1] 访问的是 i + 1 == j 的左下角,这个位置刚好用不到,默认也为0。
当 s[i] != s[j] 时,我们假定在i的左边插入一个s[j],或在j的右边插入一个s[i],然后就可以在 dp[i][j - 1] 或 dp[i + 1][j] 中找最小操作次数。
class Solution {
public:
int minInsertions(string s) {
int n = s.size();
vector<vector<int>> dp(n, vector<int>(n));
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];
}
};本篇文章的分享就到这里了,如果您觉得在本文有所收获,还请留下您的三连支持哦~