当前位置:   article > 正文

【动态规划专栏】-- 回文串问题 -- 动态规划经典题型

回文串问题

目录

动态规划

动态规划思维(基础)

状态表示(最重要)

状态转移方程(最难)

初始化(细节)

填表顺序(细节)

返回值(结果)

回文子串 ⭐⭐

【题目解析】 

【算法原理】

C++ 算法代码 

最长回文子串 ⭐⭐ 

【题目解析】 

【算法原理】

C++ 算法代码  

回文串分割Ⅳ⭐⭐⭐ 

【题目解析】 

【算法原理】

C++ 算法代码


动态规划

动态规划思维(基础)

        动态规划一般会先定义一个dp表,dp表一般为一维数组 / 二位数组。如:一维数组,会先创建一个一维数组(dp表),接下来就是想办法将这个dp填满,而填满之后里面的某一个值就是最终结果。

状态表示(最重要)

#问:是什么?

  • 就是dp[i]所代表的含义。

#问:怎么来?

  • 题目要求。
  • 经验 + 题目要求。
  • 分析问题的过程中,发现重复子问题。

状态转移方程(最难)

#问:是什么?

  • dp[i] = ?。

初始化(细节)

#问:有什么作用?

  • 保证填表的时候不越界。

        dp表是根据状态转移方程进行的,而状态转移方程是通过已有状态推出未知状态。

填表顺序(细节)

#问:有什么作用?

  • 为了填写当前状态的时候,所需要的状态已经计算过了。

返回值(结果)

        题目要求 + 状态表示。

⭐⭐⭐DP解回文串问题核心:能够将所有的字串是否是回文的信息,保存在dp表中。


回文子串 ⭐⭐

 647. 回文子串 - 力扣(LeetCode)


【题目解析】 

        为了能表示出来所有的子串,我们可以创建⼀个 n * n 的⼆维 dp 表,只用到「上三角部分」即可。 其中, dp[i][j] 表示: s 字符串 [i, j] 的子串,是否是回文串

        每层逻辑。

【算法原理】

#:状态表示:

        为了能表示出来所有的子串,我们可以创建⼀个 n * n 的⼆维 dp 表,只用到「上三角部分」
即可。 其中, dp[i][j] 表示: s 字符串 [i, j] 的子串,是否是回文串。

#:状态转移方程:

对于回文串,我们⼀般分析⼀个「区间两头」的元素:
  • 当 s[ i ] != s[ j ] 的时候:不可能是回文串, dp[ i ][ j ] = false
  • 当 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] 

#:初始化:

         因为我们的状态转移方程分析的很细致,因此无需初始化。

#:填表顺序:

        根据「状态转移方程」,我们需要「从下往上」填写每⼀行,每⼀行的顺序无所谓。

#:返回值:

        根据「状态表示和题目要求」,我们需要返回 dp 表中 true 的个数。 


C++ 算法代码 

  1. class Solution {
  2. public:
  3. int countSubstrings(string s) {
  4. int ret = 0;
  5. // 1、创建dp表
  6. vector<vector<bool>> dp(s.size(), vector<bool>(s.size(), false));
  7. // 2、初始化
  8. // 3、填表
  9. for(int i = s.size() - 1; i >= 0; i--)
  10. {
  11. for(int j = i; j < s.size(); j++)
  12. {
  13. if(s[i] == s[j])
  14. dp[i][j] = i + 1 < j ? dp[i + 1][j - 1] : true;
  15. if(dp[i][j])
  16. ret++; // 统计个数
  17. }
  18. }
  19. return ret;
  20. }
  21. };

最长回文子串 ⭐⭐ 

5. 最长回文子串 - 力扣(LeetCode)


【题目解析】 

        与上一题一样。

【算法原理】

#:状态表示:

        为了能表示出来所有的子串,我们可以创建⼀个 n * n 的⼆维 dp 表,只用到「上三角部分」
即可。 其中, dp[i][j] 表示: s 字符串 [i, j] 的子串,是否是回文串。

#:状态转移方程:

对于回文串,我们⼀般分析⼀个「区间两头」的元素:
  • 当 s[ i ] != s[ j ] 的时候:不可能是回文串, dp[ i ][ j ] = false
  • 当 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] 

#:初始化:

        因为我们的状态转移方程分析的很细致,因此无需初始化。

#:填表顺序:

        根据「状态转移方程」,我们需要「从下往上」填写每⼀行,每⼀行的顺序无所谓。

#:返回值:

        根据「状态表示和题目要求」,我们需要返回 dp 表中 true 的个数。 


C++ 算法代码  

  1. class Solution {
  2. public:
  3. string longestPalindrome(string s) {
  4. int ret_max = 0;
  5. int begin_index = 0;
  6. // 1、创建dp表
  7. vector<vector<bool>> dp(s.size(), vector<bool>(s.size(), false));
  8. // 2、初始化
  9. // 3、填表
  10. for(int i = s.size() - 1; i >= 0; i--)
  11. {
  12. for(int j = i; j < s.size(); j++)
  13. {
  14. if(s[i] == s[j])
  15. dp[i][j] = i + 1 < j ? dp[i + 1][j - 1] : true;
  16. if(dp[i][j] && j - i + 1 > ret_max)
  17. {
  18. ret_max = j - i + 1 ;
  19. begin_index = i;
  20. }
  21. }
  22. }
  23. // 4、返回值
  24. return s.substr(begin_index, ret_max);
  25. }
  26. };

回文串分割Ⅳ⭐⭐⭐ 

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


【题目解析】 

        与上题和上上题一样。

        因为其能够将所有的字串是否是回文的信息,保存在dp表中。所以我们只需要在前述中,最后加入一个判断。

【算法原理】

#:状态表示:

        为了能表示出来所有的子串,我们可以创建⼀个 n * n 的⼆维 dp 表,只用到「上三角部分」
即可。 其中, dp[i][j] 表示: s 字符串 [i, j] 的子串,是否是回文串。

#:状态转移方程:

对于回文串,我们⼀般分析⼀个「区间两头」的元素:
  • 当 s[ i ] != s[ j ] 的时候:不可能是回文串, dp[ i ][ j ] = false
  • 当 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] 

#:初始化:

        因为我们的状态转移方程分析的很细致,因此无需初始化。

#:填表顺序:

        根据「状态转移方程」,我们需要「从下往上」填写每⼀行,每⼀行的顺序无所谓。

#:返回值:

        根据「状态表示和题目要求」,我们需要返回 dp[0][i - 1] && dp[i][j] && dp[j + 1][s.size() - 1] 循环判断。 


C++ 算法代码

  1. class Solution {
  2. public:
  3. bool checkPartitioning(string s) {
  4. // 1、创建dp表
  5. vector<vector<bool>> dp(s.size(), vector<bool>(s.size(), false));
  6. // 2、初始化
  7. // 3、填表
  8. for(int i = s.size() - 1; i >= 0; i--)
  9. {
  10. for(int j = i; j < s.size(); j++)
  11. {
  12. if(s[i] == s[j])
  13. dp[i][j] = i + 1 < j ? dp[i + 1][j - 1] : true;
  14. }
  15. }
  16. // 4、返回值
  17. for(int i = 1; i < s.size() - 1; i++)
  18. {
  19. for(int j = i; j < s.size() - 1; j++)
  20. {
  21. if(dp[0][i - 1] && dp[i][j] && dp[j + 1][s.size() - 1])
  22. return true;
  23. }
  24. }
  25. return false;
  26. }
  27. };
声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/繁依Fanyi0/article/detail/660205
推荐阅读
相关标签
  

闽ICP备14008679号