动态规划解决回文子串问题

admin管理员组

文章数量:1794759

动态规划解决回文子串问题

前言：

回文串相关问题在我们的算法题中算是老生常谈，本文主要介绍如何使用动态规划的思路去解决回文串系列问题。

总体思路：

能够将所有的子串是否是回文的信息，存储在二维dp表中。有了这个dp表，就可以将hard难度转化为easy难度！

接下来我们按照动态规划五板斧去解决~

1、状态表示

dp[i][j]表示s字符串[i, j] 的子串，是否是回文串。（其中i <= j）

2、状态转移方程

我们根据s[i] 和 s[j] 是否相等来判断dp[i][j]的信息。分两种情况

• 当s[i] != s[j] 时，dp[i][j] 存储 false，表示s[i] ~ s[j] 之间的字符串不是回文串。
• 当s[i] == s[j] 时，分为三种情况：

1. 当 i == j ，表示单个字符，肯定是回文串
2. 当i + 1 == j ，表示两个字符相邻，肯定也是回文串
3. 不是上述两种情况时，根据dp[i+1][j-1]来判断，与他相等

3、初始化

无需初始化，不会有越界问题

4、填表顺序

从下往上填写每一行。并且要保证i <= j ,所以两层for循环中，内层初始值 j 就是外层的 i

5、返回值

当我们将dp表填完之后，就可以根据题目要求进行解决！

---

下面带来一道例题：

647. 回文子串

解析：

将dp表填完之后，直接计数表中true个数即可！秒杀！！！

原码：

代码语言：javascript代码运行次数：0运行复制

class Solution {
public:
    int countSubstrings(string s) {
        int n = s.size();
        vector<vector<bool>> dp(n, vector<bool>(n));
        //本题不需要初始化
        
        //从下往上初始化dp表
        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] = false;
                else
                {
                    if(i == j || i+1 == j) dp[i][j] = true;
                    else
                    {
                        dp[i][j] = dp[i+1][j-1];
                    }
                }
                if(dp[i][j] == true) ret++;
            }
        }
        return ret;
    }
};

本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。 原始发表：2024-10-15，如有侵权请联系 cloudcommunity@tencent 删除前往查看dp动态规划算法字符串存储

本文标签： 动态规划解决回文子串问题