荥阳网站制作,有哪些小公司网站,合肥网站seo整站优化,网络代码#x1f496;作者#xff1a;小树苗渴望变成参天大树#x1f388; #x1f389;作者宣言#xff1a;认真写好每一篇博客#x1f4a4; #x1f38a;作者gitee:gitee✨ #x1f49e;作者专栏#xff1a;C语言,数据结构初阶,Linux,C 动态规划算法#x1f384; 如 果 你 … 作者小树苗渴望变成参天大树 作者宣言认真写好每一篇博客 作者gitee:gitee✨ 作者专栏C语言,数据结构初阶,Linux,C 动态规划算法 如 果 你 喜 欢 作 者 的 文 章 就 给 作 者 点 点 关 注 吧 文章目录 前言第三十五题[647. 回文子串](https://leetcode.cn/problems/palindromic-substrings/)第三十六题[5. 最长回文子串](https://leetcode.cn/problems/longest-palindromic-substring/)第三十七题[1745. 分割回文串 IV](https://leetcode.cn/problems/palindrome-partitioning-iv/)第三十八题[132. 分割回文串 II](https://leetcode.cn/problems/palindrome-partitioning-ii/)第三十九题[516. 最长回文子序列](https://leetcode.cn/problems/longest-palindromic-subsequence/)第四十题[1312. 让字符串成为回文串的最少插入次数](https://leetcode.cn/problems/minimum-insertion-steps-to-make-a-string-palindrome/) 前言
今天博主来讲解动态规划的另一个题型就是回文串问题这个系列的问题套路差不多首先大家要了解什么是回文串就是在原串中选出连续的一个子串判断是不是回文的即可接下来我们将会一题题的给大家进行讲解话不多说我们开始进入正文 第三十五题647. 回文子串
题目解析
动态规划算法
1. 状态表示经验题目要求 做这个系列的问题我们就是将子串是否为回文的结果放到dp表里面因为你要插进来的字符是否和前面构成回文首先保证前面的子串是回文才行所以我们的dp表需要一个二维的表示回文子串的起始和结尾 dp[i][j]表示以i,j位置为结尾的子串是否为回文子串(ij) 2. 状态转移方程
3. 初始化保证数组不越界 我们j是大于等于i的但是会越界的情况已经单独拿出来分析了所以不用初始化 4. 填表顺序 所以我们要从上往下进行填表 5. 返回值: 返回为真的个数就可以了 代码实现
class Solution {
public:int countSubstrings(string s) {int ns.size();vectorvectorbool dp(n,vectorbool(n));int count0;for(int in-1;i0;i--){for(int ji;jn;j){if(s[i]s[j]){if(ij||i1j)dp[i][j]true;elsedp[i][j]dp[i1][j-1];}if(dp[i][j]true) count;}}return count;}
};运行结果 这一题可以说是为后面的题目做铺垫相当于一个引子 第三十六题5. 最长回文子串
题目解析 此题就是找到最长回文子串做法和上一题一模一样先用dp表存放是否构成回文串有起始位置和结束位置就可以算出来长度。 动态规划算法
1. 状态表示经验题目要求 dp[i][j]表示以i,j位置为结尾的子串是否为回文子串(ij) 2. 状态转移方程 每次填完dp表的时候就计算一个长度i表示起始位置j表示结束位置长度为j-i1, 3. 初始化保证数组不越界 我们j是大于等于i的但是会越界的情况已经单独拿出来分析了所以不用初始化 4. 填表顺序 所以我们要从上往下进行填表 5. 返回值: 将长度和起始位置算出来通过substr来获取子串返回即可 代码实现
class Solution {
public:string longestPalindrome(string s) {int ns.size();vectorvectorbool dp(n,vectorbool(n));int len1,start0;for(int in-1;i0;i--){for(int ji;jn;j){if(s[i]s[j]){if(ij||i1j)dp[i][j]true;elsedp[i][j]dp[i1][j-1];}if(dp[i][j]lenj-i1)//选出最长的回文子串{lenj-i1,starti;}}}return s.substr(start,len);}
};运行结果 第三十七题1745. 分割回文串 IV
题目解析 这个题目还是非常的好理解的因为有固定的数分成三个回文子串。 先将子串是否为回文子串放到dp表里面然后再枚举dp表就行了。 这题我就不详细讲解了直接上代码了 代码实现
class Solution {
public:bool checkPartitioning(string s) {int ns.size();vectorvectorbool dp(n,vectorbool(n));int count0;for(int in-1;i0;i--)//将子串是否是文回放到dp表里面{for(int ji;jn;j){if(s[i]s[j]){if(ij||i1j)dp[i][j]true;elsedp[i][j]dp[i1][j-1];}}}for(int i1;in-1;i)//第一个至少要留出来一个位置{for(int ji;jn-1;j)//最后一个也要留出来一个位置{if(dp[i][j]dp[0][i-1]dp[j1][n-1])return true;}}return false;}
};运行结果 第三十八题132. 分割回文串 II
题目解析 动态规划算法
1. 状态表示经验题目要求 我们以某一个位置来考虑问题 dp[i]表示从0开始到以i位置为结尾的子串中将子串分割成每个部分都是回文子串的最少的切割次数 2. 状态转移方程 这题和单词拆分的思想有点像再[0,i]区间中选择一个j此时j位置就是最后一刀切割的地方前面切割的次数加上最后一刀就是总次数 3. 初始化保证数组不越界 j-1是不会越界的j0的。 因为要保证第一次求最小值的时候不能干扰到选择dp[j-1]1所以不初始化就为01那么最小值一直都是0,所以干脆就初始化为最大值。
4. 填表顺序 从左往右 5. 返回值: 返回dp[n-1];
代码实现
class Solution {
public:int minCut(string s) {int ns.size();vectorvectorbool isPal(n,vectorbool(n));int count0;for(int in-1;i0;i--)//将子串是否是文回放到dp表里面{for(int ji;jn;j){if(s[i]s[j]){if(ij||i1j)isPal[i][j]true;elseisPal[i][j]isPal[i1][j-1];}}}//创建dp表初始化vectorint dp(n,INT_MAX);for(int i0;in;i){if(isPal[0][i]){dp[i]0;}else{for(int j1;ji;j)if(isPal[j][i])dp[i]min(dp[j-1]1,dp[i]);} } //返回值return dp[n-1];}
};运行结果 第三十九题516. 最长回文子序列
题目解析
动态规划算法
1. 状态表示经验题目要求 dp[i]表示以i位置元素为结尾的子序列中最长的回文子序列的长度 上面的状态表示不行我们要重新定义状态表示定义两个位置 dp[i][j]表示s字符串里面【ij】子区间内的所有子序列中最长回文子序列的长度 2. 状态转移方程
3. 初始化保证数组不越界 我们看到会使用到使用到j-1或者i1位置的值
4. 填表顺序 我们会使用到 dp[i1][j]正下方的值 dp[i][j-1]左边的值 dp[i1][j-1]左下方的值 从下往上从左往右 5. 返回值: 返回整个字符串区间dp[0][n-1]
代码实现
class Solution {
public:int longestPalindromeSubseq(string s) {int ns.size();//创建dp表vectorvectorint dp(n,vectorint(n));for(int in-1;i0;i--)//从下往上{dp[i][i]1;//此情况肯定是相等的for(int ji1;jn;j)//从左往右{if(s[i]s[j])dp[i][j]dp[i1][j-1]2; //放在一起考虑了 else dp[i][j]max(dp[i][j-1],dp[i1][j]);//不相等的时候}}//返回值return dp[0][n-1];}
};运行结果 第四十题1312. 让字符串成为回文串的最少插入次数
题目解析 这题还是按照上一题的分析方式一样选择一个区间去分析。 动态规划算法
1. 状态表示经验题目要求 dp[i][j]表示s字符串以[i,j]区间内想要变成回文串要插入的最少次数 2. 状态转移方程
3. 初始化保证数组不越界 根据上题的分析无需初始化 4. 填表顺序 从下往上从左往右 5. 返回值: dp[0][n-1]; 代码实现
class Solution {
public:int minInsertions(string s) {int ns.size();//创建dp表vectorvectorint dp(n,vectorint(n));for(int in-1;i0;i--)//从下往上for(int ji1;jn;j)//从左往右从i1位置因为ij的情况为0不需要考虑if(s[i]s[j])dp[i][j]dp[i1][j-1];else dp[i][j]min(dp[i][j-1],dp[i1][j])1;//返回值return dp[0][n-1];}
};运行结果 到这里我们的回文串问题就讲解完毕了这类题型之间的练习都挺大了上一题的经验可以大量的运用到下一题上这给我们的学习也带来了很大的帮助但凡不是一题题做过来的那么后面的每一题都很难想到所以我们要善于总结这样下次单独碰到一题就不会没有头绪好了我们今天的题目就先讲解到这里了我们下篇介绍关于两个数组的dp问题。
