专题二十三_动态规划_回文串系列问题_算法专题详细总结
目录
动态规划
经过前面几个专题的学习，特别是子数组系列、子序列问题等的动态规划，我相信到这里大家都有了质的飞跃，现在进入回文串系列问题，一定能有很多收获的~
回文串系列问题
1. 回⽂⼦串（medium）
解析：
解决回文串问题，这里提供三个思路：
1.中心扩展法：n^2 / 1
2.马拉车算法：n / n
3.动态规划算法：n^2 / n^2
这里的中心扩展法是最简单的一种算法，一般适用于简单的求解单个字符串是否是回文串的问题；其中马拉车算法是一种很复杂但是很优的算法，只能解决回文串这一种问题，而且学习成本很高，所以这里还是不推荐，如果你有强烈欲望，可以自己学习一下；再就是动态规划思想，是虽然这里的时间复杂度和空间复杂度都很高，但是我们学习的是这一种算法思想，通过动态规划的思想就能很轻松的将困难题变成简单题~
1.状态表达式：
由于一个字符串要有头尾两个字符才能判断当前的字符串是否是回文串：
所以要设置dp[i][j]表示：以i位置为开头，j位置为结尾的字符串是否是回文串
这样就可以将整个字符串的所有有两个字符位置表示的子串都在一个二维数组内表示出来；
2.状态转移方程：
只有在s[i] == s[j] 的时候才有讨论当前子串是否为回文串的意义，所以分三类讨论：
1.当i == j 时 两字符重叠，是回文串
2.当i+1 == j 时 s[i] == s[j] 并且两字符相邻，所以是回文串
3.当s[i] == s[j]，但是两字符不相邻，所以就要缩小范围，来继续判断【i+1,j-1】这个范围内的字符串是否是回文串
3.初始化：
无需初始化，因为不会存在越界的问题，通过状态表达式，只需要判断当前位置dp[i][j]是否是满足回文串的问题
4.填表顺序：
由于dp内只存在这两种位置的访问情况，所以必须要先直到【i+1,j-1】才能知道【i,j】这个位置，所以填表顺序是从下往上，从左往右填表；即行数i倒着填，列数j正着填
5.返回值：
最后用ret统计dp内有多少个true即可
代码编写:
class Solution {
public:
int countSubstrings(string s) {
int n=s.size();
vector<vector<int>> dp(n,vector<int>(n));
int ret=0;
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]=1;
else if(i+1<n&&j-1>=0) dp[i][j]=dp[i+1][j-1];
}
if(dp[i][j]) ret++;
}
}
return ret;
}
};总结：
由上面给出的求解回文串的三种方法中，动态规划思想是一种极为重要的思路，通过这题就可以看出动态规划思路很清晰明了，可以很简单的就将hard转换为easy
2. 最⻓回⽂⼦串（medium）
解析：
这一题的思路简直跟上一题一模一样，只是返回的内容不同，我们同样是要遍历所有的二维数组，就是遍历所有子串的情况，然后来判断当前位置是否满足回文串的条件，最后返回最长的即可：
1.状态表达式：
由于一个字符串要有头尾两个字符才能判断当前的字符串是否是回文串：
所以要设置dp[i][j]表示：以i位置为开头，j位置为结尾的字符串是否是回文串
这样就可以将整个字符串的所有有两个字符位置表示的子串都在一个二维数组内表示出来；
2.状态转移方程：
只有在s[i] == s[j] 的时候才有讨论当前子串是否为回文串的意义，所以分三类讨论：
1.当i == j 时 两字符重叠，是回文串
2.当i+1 == j 时 s[i] == s[j] 并且两字符相邻，所以是回文串
3.当s[i] == s[j]，但是两字符不相邻，所以就要缩小范围，来继续判断【i+1,j-1】这个范围内的字符串是否是回文串
3.初始化：
无需初始化，因为不会存在越界的问题，通过状态表达式，只需要判断当前位置dp[i][j]是否是满足回文串的问题
4.填表顺序：
由于dp内只存在这两种位置的访问情况，所以必须要先直到【i+1,j-1】才能知道【i,j】这个位置，所以填表顺序是从下往上，从左往右填表；即行数i倒着填，列数j正着填
5.返回值：
只需要返回最长的回文串即可，那么就要ret来记录最长的长度，_ret来记录当前最长的子字符串即可，返回_ret
代码编写：
class Solution {
public:
string longestPalindrome(string s) {
int n=s.size(),ret=0;
vector<vector<int>> dp(n,vector<int>(n));
string _ret;
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]=1;
else if(i+1<n&&j-1>=0) dp[i][j]=dp[i+1][j-1];
if(dp[i][j]&&j-i+1>ret)
{
ret=j-i+1;
_ret=s.substr(i,ret);
}
}
}
}
return _ret;
}
};总结：
回文串系列的题目还是非常好想的，只要弄明白一题，后面就是照搬原样即可；
3. 回⽂串分割IV（hard）
将一个字符串分割成三块，如果这三块都是回文串，就直接返回true；否则返回false
解析：
这一题我们先要有一个整体的思路，肯定就是先要判断所有情况下的子字符串是否满足回文串，即设计二维数组来遍历所有下标，然后再来一个双重for将整个字符串分为3块，直接判断是否都是回文串并进行返回即可；
1.状态表达式：
由于一个字符串要有头尾两个字符才能判断当前的字符串是否是回文串：
所以要设置dp[i][j]表示：以i位置为开头，j位置为结尾的字符串是否是回文串
这样就可以将整个字符串的所有有两个字符位置表示的子串都在一个二维数组内表示出来；
2.状态转移方程：
只有在s[i] == s[j] 的时候才有讨论当前子串是否为回文串的意义，所以分三类讨论：
1.当i == j 时 两字符重叠，是回文串
2.当i+1 == j 时 s[i] == s[j] 并且两字符相邻，所以是回文串
3.当s[i] == s[j]，但是两字符不相邻，所以就要缩小范围，来继续判断【i+1,j-1】这个范围内的字符串是否是回文串
3.初始化：
无需初始化，因为不会存在越界的问题，通过状态表达式，只需要判断当前位置dp[i][j]是否是满足回文串的问题
4.填表顺序：
由于dp内只存在这两种位置的访问情况，所以必须要先直到【i+1,j-1】才能知道【i,j】这个位置，所以填表顺序是从下往上，从左往右填表；即行数i倒着填，列数j正着填
5.返回值：
要返回当前位置进行分割的三块字符串是否满足全是回文串，所以分割后的下标是暴力求解：
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;
}
}代码编写：
class Solution {
public:
bool checkPartitioning(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;j<n;j++)
{
if(s[i]==s[j])
{
// if(i==j||i+1==j) dp[i][j]=true;
// else if(i+1<n&&j-1>=0) dp[i][j]=dp[i+1][j-1];
dp[i][j]=i+1<j?dp[i+1][j-1]:true;
}
}
}
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;
}
};总结：
这一道hard题用动态规划的思路真的变的很简单，依旧是求出所有子串是否能成为回文串，然后再判断字符串分三块的问题直接暴力求解ok，所以这种思路一定要掌握，多复习也就记住了~
4. 分割回⽂串II（hard）
解析：
1.状态表达式：
dp[i]表示：在s[0,i]位置上形成回文串的最少分割次数
2.状态转移方程：
dp[i] = min(dp[j - 1] + 1, dp[i]);
3.初始化：
由于dp表内是要求最小分割次数，每次都要取min，所以dp表内都初始化为INT_MAX
4.填表顺序：
从左往右填
5.返回值：
返回dp[n-1]
代码编写：
class Solution {
public:
int minCut(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; j < n; j++)
if (s[i] == s[j])
dp[i][j] = i + 1 < j ? dp[i + 1][j - 1] : true;
vector<int> _dp(n, INT_MAX / 2);
for (int i = 0; i < n; i++) {
if (dp[0][i])
_dp[i] = 0;
else {
for (int j = 1; j <= i; j++) {
if (dp[j][i])
_dp[i] = min(_dp[j - 1] + 1, _dp[i]);
}
}
}
return _dp[n - 1];
}
};总结：
这一题主要就是要想清楚怎么定义状态表达式，要明白了状态表达式的定义，说明出以i位置为结尾的最大分割次数，从而引出[0,i]是否是一整个回文，是就是0次；不是，就在进行判断，[1,j](0<j<=i) 判断当dp[j][i]这个位置是否为回文，是才能继续判断_dp[j-1]前面的最少分割次数
5. 最⻓回⽂⼦序列（medium）
解析：
1.状态表达式：
dp[i]表示：以i位置为结尾的最长回文子序列的长度；
dp[i][j]表示：在s[i,j]区间内最长的回文子序列的长度
2.状态转移方程：
if(s[i]==s[j])
{
if(i==j) dp[i][j]=1;
else if(i+1==j) dp[i][j]=2;
else dp[i][j]=dp[i+1][j-1]+2;
}
else
dp[i][j]=max(dp[i][j-1],dp[i+1][j]);3.初始化：
不用初始化，因为求最长的长度，开始为0/1都可以
4.填表顺序：
由于dp内只存在这两种位置的访问情况，所以必须要先直到【i+1,j-1】才能知道【i,j】这个位置，所以填表顺序是从下往上，从左往右填表；即行数i倒着填，列数j正着填
5.返回值：
dp[0][n-1]
代码编写：
class Solution {
public:
int longestPalindromeSubseq(string s) {
int n=s.size();
vector<vector<int>> dp(n,vector<int>(n,1));
int ret=0;
for(int i=n-1;i>=0;i--)
{
for(int j=i;j<n;j++)
{
if(s[i]==s[j])
{
if(i==j) dp[i][j]=1;
else if(i+1==j) dp[i][j]=2;
else 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]，这样更加便捷，因为关于子序列的判断就是求在s[i,j]这个区间内的回文子序列的长度大小，然后进行分类讨论，当s[i]==s[j] 和 s[i]!=s[j]两种情况下如何求出最长回文子序列的长度
6. 让字符串成为回⽂串的最⼩插⼊次数（hard）
插入最少的次数，让该字符串成为回文串
解析：
1.状态表达式：
2.状态转移方程：
在分别判断当s[i] == s[j] 和 s[i]!=s[j]时两者的讨论方式：
由于在s[i]!=s[j]的时候，dp[i][j-1] 和 dp[i+1][j]这两个区间内都要进行一次插入，让两端的字符相等
if(s[i]==s[j]) dp[i][j]=i+1<j?dp[i+1][j-1]:0;
else dp[i][j]=min(dp[i][j-1],dp[i+1][j])+1;3.初始化：
不用初始化
4.填表顺序：
从下往上，从左往右填
5.返回值：
返回dp[0][n-1];
代码编写：
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;j<n;j++)
{
if(s[i]==s[j]) dp[i][j]=i+1<j?dp[i+1][j-1]:0;
else dp[i][j]=min(dp[i][j-1],dp[i+1][j])+1;
}
}
return dp[0][n-1];
}
};总结：
这一题其实仔细总结一下，跟以前做的题目简直一模一样，只要考虑求出状态表达式和转移方程，那简直不要太轻松
总结不易~本节对我有很大帮助和收获，希望对你也是~！！！
原文地址：https://blog.csdn.net/2301_80636070/article/details/144033532
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！