【十三】【动态规划】1745. 分割回文串 IV、132. 分割回文串 II、516. 最长回文子序列,三道题目深度解析

本文主要是介绍【十三】【动态规划】1745. 分割回文串 IV、132. 分割回文串 II、516. 最长回文子序列,三道题目深度解析,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

动态规划

动态规划就像是解决问题的一种策略,它可以帮助我们更高效地找到问题的解决方案。这个策略的核心思想就是将问题分解为一系列的小问题,并将每个小问题的解保存起来。这样,当我们需要解决原始问题的时候,我们就可以直接利用已经计算好的小问题的解,而不需要重复计算。

动态规划与数学归纳法思想上十分相似。

数学归纳法:

  1. 基础步骤(base case):首先证明命题在最小的基础情况下成立。通常这是一个较简单的情况,可以直接验证命题是否成立。

  2. 归纳步骤(inductive step):假设命题在某个情况下成立,然后证明在下一个情况下也成立。这个证明可以通过推理推断出结论或使用一些已知的规律来得到。

通过反复迭代归纳步骤,我们可以推导出命题在所有情况下成立的结论。

动态规划:

  1. 状态表示:

  2. 状态转移方程:

  3. 初始化:

  4. 填表顺序:

  5. 返回值:

数学归纳法的基础步骤相当于动态规划中初始化步骤。

数学归纳法的归纳步骤相当于动态规划中推导状态转移方程。

动态规划的思想和数学归纳法思想类似。

在动态规划中,首先得到状态在最小的基础情况下的值,然后通过状态转移方程,得到下一个状态的值,反复迭代,最终得到我们期望的状态下的值。

接下来我们通过三道例题,深入理解动态规划思想,以及实现动态规划的具体步骤。

1745. 分割回文串 IV - 力扣(LeetCode)

题目解析

状态表示

状态表示通常由经验+题目要求得到,

经验一般指以某个位置为结尾,或者以某个位置为开始。

我们需要判断(i,j)子数组是否属于回文子数组,可以定义dp[i][j]表示(i,j)子数组是否属于回文子数组。

状态转移方程

我们希望(i,j)位置的状态能够通过其他位置的状态推导出来。

针对于(i,j)位置的状态进行分析。

  1. 如果nums[i]==nums[j],

    1. 如果(i,j)子数组只有一个元素,即i==j, 只有一个元素属于回文子数组情况,故dp[i][j]=true。

    2. 如果(i,j)子数组只有两个元素,即i+1==j, 此时符合回文子数组的定义,故dp[i][j]=true。

    3. 如果(i,j)子数组有3个或3个以上的元素,即i+1<j, 此时,如果(i+1,j-1)子数组可以构成回文子数组,那么(i,j)子数组就可以构成回文子数组。 故,dp[i][j]=dp[i+1][j-1]。

  2. 如果nums[i]!=nums[j], 此时不可能构成回文子数组,所以dp[i][j]=false。

对上述情况进行合并和简化,

如果我们对所有位置状态初始化为false,我们就只需要判断nums[i]==nums[j]的情况,

此时的状态转移方程为,

 
       if(s[i]==s[j]){dp[i][j] = i + 1 < j ? dp[i + 1][j - 1] : true;}

初始化

根据状态转移方程,我们知道推导(i,j)位置的状态时,可能需要用到dp[i+1][j-1]位置的状态, 如果i+1<j,此时需要保证(i+1,j-1)对应下标不会越界,并且此时(i+1,j-1)位置状态已经填写完毕。

先考虑填表顺序,我们知道i介于(0,n-1)之间,j介于(i,n-1)之间,所以i+1介于(1,n)之间且i+1<j,所以i+1介于(1,n-1)之间,i+1不会越界。

又j介于(i,n-1)之间,j-1介于(i-1,n-2)之间,又j-1>i,所以j-1也不会越界。

要保证此时(i+1,j-1)位置状态已经填写完毕,只需要控制填报顺序即可。

所以我们需要初始化所有位置状态为false即可,也就是在状态转移方程中分析的初始化。

填表顺序

根据状态转移方程,我们知道推导(i,j)位置的状态时,可能需要用到dp[i+1][j-1]位置的状态, 所以在填写(i,j)位置状态时,需要保证(i+1,j-1)位置状态已经填写完毕。

  1. 如果固定i填写j, 那么i的变化一定要从大到小,此时当我们填写(i,j)位置的状态时,(i+1,)位置的状态已经填写完毕,所以j的变化可以从大到小也可以从小到大。

  2. 如果固定j填写i, 那么j的变化一定要从小到大,此时当我们填写(i,j)位置的状态时,(,j-1)位置的状态已经填写完毕,所以i'的变化可以从大到小也可以从小到大。

如果我们选择固定i填写j,得到

 
    for(int i=n-1;i>=0;i--){for(int j=i;j<=n-1;j++){}}

返回值

dp[i][j]表示(i,j)子数组是否属于回文子数组。

dp状态的填写只完成了第二步的工作,即快速判断(i,j)子数组是否为回文子数组。

还有一步,就是使(a,b)遍历所有情况。

如果有一种情况三部分都是回文子数组,就返回true,否则就返回false。

代码实现

 
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 = 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 - 力扣(LeetCode)

题目解析

状态表示

状态表示通常由经验+题目要求得到,

经验一般指以某个位置为结尾,或者以某个位置为开始。

我们很容易可以定义这样一个状态表示,定义dp[i]表示在(0,i)区间上的字符串,最少的分割次数。

状态转移方程

我们针对于最后一个位置的状态进行分析,看看i位置状态能不能由其他位置的状态推导得出,定义0<=j<=i,那我们可以根据(j,i)位置上的子串是否是回文串分成下面两种情况,

  1. 如果(j,i)可以构成回文串, i位置的状态就等于j-1位置上的状态+1,即dp[i]=dp[j-1]+1。

  2. 如果(j,i)不能构成回文串, 此时j的位置不需要考虑。

因为dp[i]要的是最小的分割次数,所以j需要遍历(0~i-1)。

因为我们需要快速判断(j,i)位置是否属于回文字符串,所以我们可以先创建一个dp表,dp[i][j]表示(i,j)字符串是否构成回文字符串。用来存储是否可以构成回文字符串的信息。

根据上述分析,我们知道要推导i位置的状态,可能需要用到j-1位置的状态。

所以i的变化应该是从小到大,即(0~n-1)。

令j-1>=0得j>=1,只有j>=1的时候才不会越界。所以我们需要控制j介于(1,i)之间。

独立判断(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])dp[i] = min(dp[i], dp[j - 1] + 1);}}

初始化

带入最初始的推导,即i=0,发现dp[i] 可以正常推导,而后续的状态都可以根据前面已经推导的状态进行推导得出,所以不需要进行初始化。

填表顺序

从左往右

返回值

dp[i]表示在(0,i)区间上的字符串,最少的分割次数。

题目要求我们找到(0,n-1)区间上的字符串,最少的分割次数,

所以返回dp[n-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++)isPal[i][j] = s[i] == s[j] ? (i + 1 < j ? isPal[i + 1][j - 1] : true): false;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[i], dp[j - 1] + 1);}}return dp[n - 1];}
};

516. 最长回文子序列 - 力扣(LeetCode)

题目解析

状态表示

状态表示一般通过经验+题目要求得到,

经验一般指以某个位置为结尾,或者以某个位置为开始。

题目要求我们找回文子序列,根据以前的经验,和回文有关的问题,我们的状态表示研究的对象一

般都是选取原字符串中的一段区域[i,j]内部的情况来研究。

所以我们可以定义dp[i][j]表示s字符串[i,j]区间内所有子序列中,最长的回文序列长度。

状态转移方程

我们针对于最后一个位置的状态进行分析,看看i位置状态能不能由其他位置的状态推导得出。

如果紫色的字符串可以构成回文串,那么我们在紫色字符串两端添加相同的蓝色元素,整个字符串同样可以构成回文串。

根据这种思维,我们可以根据i,j两个位置的元素是否相等进行分析。

  1. 如果s[i]==s[j], 那么[i,j]区间上的最长回文子序列,应该是 [i+1,j-1] 区间上的最长回文子序列首尾加上s[i],s[j]两个元素,此时dp[i][j]=dp[i+1][j-1]+2。

  2. 如果s[i]!=s[j], 说明[i,j]区间上的回文子序列不可能同时取到i,j两个位置上的元素。

    1. 如果i位置元素不取, 此时[i,j]区间上的最长回文子序列的长度,应该是[i+1,j]区间上的最长回文子序列的长度。即dp[i][j]=dp[i+1][j]。

    2. 如果j位置元素不取, 此时[i,j]区间上的最长回文子序列的长度,应该是[i,j-1]区间上的最长回文子序列的长度。即dp[i][j]=dp[i][j-1]。

第二种情况下,dp中存储的是最长的回文子序列的长度,所以dp[i][j]=max(dp[i+1][j],dp[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][j - 1],dp[i + 1][j])

初始化

根据状态转移方程,我们知道想要推导(i,j)位置的状态,可能需要用到(i+1,j-1),(i,j-1),(i+1,j)位置上的状态。

我们先判断填表顺序,

  1. 如果固定i改变j, 那么i的变化一定从大到小,因为可能用到(i,j-1)位置的状态,所以j的变化需要从小到大。

  2. 如果固定j改变i, 那么j的变化一定从小到大,因为可能用到(i+1,j)位置的状态,所以i的变化需要从大到小。

所以我们可以得到完整的状态转移方程,

 
        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;elsedp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);}}

我们把最初迭代情况带入迭代代码中,即i=n-1,j=n,此时得到dp[n-1][n-1]=1。

而后续的状态都可以根据前面的状态推导得出,所以我们不需要进行初始化。

填表顺序

  1. 如果固定i改变j, 那么i的变化一定从大到小,因为可能用到(i,j-1)位置的状态,所以j的变化需要从小到大。

  2. 如果固定j改变i, 那么j的变化一定从小到大,因为可能用到(i+1,j)位置的状态,所以i的变化需要从大到小。

返回值

dp[i][j]表示s字符串[i,j]区间内所有子序列中,最长的回文序列长度。

根据题目要求,我们需要得到[0,n-1]区间内所有子序列中,最长的回文子序列长度。

所以返回dp[0][n-1]。

代码实现

 
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;elsedp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);}}return dp[0][n - 1];}
};

结尾

今天我们学习了动态规划的思想,动态规划思想和数学归纳法思想有一些类似,动态规划在模拟数学归纳法的过程,已知一个最简单的基础解,通过得到前项与后项的推导关系,由这个最简单的基础解,我们可以一步一步推导出我们希望得到的那个解,把我们得到的解依次存放在dp数组中,dp数组中对应的状态,就像是数列里面的每一项。最后感谢您阅读我的文章,对于动态规划系列,我会一直更新,如果您觉得内容有帮助,可以点赞加关注,以快速阅读最新文章。

最后,感谢您阅读我的文章,希望这些内容能够对您有所启发和帮助。如果您有任何问题或想要分享您的观点,请随时在评论区留言。

同时,不要忘记订阅我的博客以获取更多有趣的内容。在未来的文章中,我将继续探讨这个话题的不同方面,为您呈现更多深度和见解。

谢谢您的支持,期待与您在下一篇文章中再次相遇!

这篇关于【十三】【动态规划】1745. 分割回文串 IV、132. 分割回文串 II、516. 最长回文子序列,三道题目深度解析的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/567490

相关文章

网页解析 lxml 库--实战

lxml库使用流程 lxml 是 Python 的第三方解析库,完全使用 Python 语言编写,它对 XPath表达式提供了良好的支 持,因此能够了高效地解析 HTML/XML 文档。本节讲解如何通过 lxml 库解析 HTML 文档。 pip install lxml lxm| 库提供了一个 etree 模块,该模块专门用来解析 HTML/XML 文档,下面来介绍一下 lxml 库

第10章 中断和动态时钟显示

第10章 中断和动态时钟显示 从本章开始,按照书籍的划分,第10章开始就进入保护模式(Protected Mode)部分了,感觉从这里开始难度突然就增加了。 书中介绍了为什么有中断(Interrupt)的设计,中断的几种方式:外部硬件中断、内部中断和软中断。通过中断做了一个会走的时钟和屏幕上输入字符的程序。 我自己理解中断的一些作用: 为了更好的利用处理器的性能。协同快速和慢速设备一起工作

动态规划---打家劫舍

题目: 你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警。 给定一个代表每个房屋存放金额的非负整数数组,计算你 不触动警报装置的情况下 ,一夜之内能够偷窃到的最高金额。 思路: 动态规划五部曲: 1.确定dp数组及含义 dp数组是一维数组,dp[i]代表

【C++】_list常用方法解析及模拟实现

相信自己的力量,只要对自己始终保持信心,尽自己最大努力去完成任何事,就算事情最终结果是失败了,努力了也不留遗憾。💓💓💓 目录   ✨说在前面 🍋知识点一:什么是list? •🌰1.list的定义 •🌰2.list的基本特性 •🌰3.常用接口介绍 🍋知识点二:list常用接口 •🌰1.默认成员函数 🔥构造函数(⭐) 🔥析构函数 •🌰2.list对象

poj3261(可重复k次的最长子串)

题意:可重复k次的最长子串 解题思路:求所有区间[x,x+k-1]中的最小值的最大值。求sa时间复杂度Nlog(N),求最值时间复杂度N*N,但实际复杂度很低。题目数据也比较水,不然估计过不了。 代码入下: #include<iostream>#include<algorithm>#include<stdio.h>#include<math.h>#include<cstring

csu1328(近似回文串)

题意:求近似回文串的最大长度,串长度为1000。 解题思路:以某点为中心,向左右两边扩展,注意奇偶分开讨论,暴力解即可。时间复杂度O(n^2); 代码如下: #include<iostream>#include<algorithm>#include<stdio.h>#include<math.h>#include<cstring>#include<string>#inclu

poj 3974 and hdu 3068 最长回文串的O(n)解法(Manacher算法)

求一段字符串中的最长回文串。 因为数据量比较大,用原来的O(n^2)会爆。 小白上的O(n^2)解法代码:TLE啦~ #include<stdio.h>#include<string.h>const int Maxn = 1000000;char s[Maxn];int main(){char e[] = {"END"};while(scanf("%s", s) != EO

uva 10055 uva 10071 uva 10300(水题两三道)

情歌两三首,水题两三道。 好久没敲代码了为暑假大作战热热身。 uva 10055 Hashmat the Brave Warrior 求俩数相减。 两个debug的地方,一个是longlong,一个是输入顺序。 代码: #include<stdio.h>int main(){long long a, b;//debugwhile(scanf("%lld%lld", &

软考系统规划与管理师考试证书含金量高吗?

2024年软考系统规划与管理师考试报名时间节点: 报名时间:2024年上半年软考将于3月中旬陆续开始报名 考试时间:上半年5月25日到28日,下半年11月9日到12日 分数线:所有科目成绩均须达到45分以上(包括45分)方可通过考试 成绩查询:可在“中国计算机技术职业资格网”上查询软考成绩 出成绩时间:预计在11月左右 证书领取时间:一般在考试成绩公布后3~4个月,各地领取时间有所不同

uva 10131 最长子序列

题意: 给大象的体重和智商,求体重按从大到小,智商从高到低的最长子序列,并输出路径。 代码: #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cstring>#include <cmath>#include <stack>#include <vect