【动态规划】回文串问题

这篇具有很好参考价值的文章主要介绍了【动态规划】回文串问题。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

动态规划(回文串问题)

1. 回文子串

题目链接

  1. 状态表示

    f[i][j]表示 i 到 j 的子串当中是否是回文

  2. 状态转移方程

    【动态规划】回文串问题,动态规划,算法

  3. 初始化

    最初所有的内容都是0即可

  4. 填表

    因为 i j 需要用 i + 1 来初始化,所以这个时候需要从下往上填表

  5. 返回值

    返回整个dp 表里true 的数目就可以

AC代码:

class Solution 
{
public:
    int countSubstrings(string s) 
    {
        int n = s.size();
        vector<vector<bool>> dp(n, vector<bool>(n));
        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] = i + 1 < j ? dp[i + 1][j - 1] : true;
                }
                if (dp[i][j]) ret++;
            }
        }
        return ret;
    }
};

2. 最长回文子串

题目链接

如果需要求一个字符串当中的最长的回文子串,需要将所有的回文子串找到,然后再所有的回文子串里面找打一个最长的就可以了

可以参考上一个题目回文子串

AC代码:文章来源地址https://www.toymoban.com/news/detail-702292.html

class Solution 
{
public:
    string longestPalindrome(string s) 
    {
        // 找到所有的回文子串
        int n = s.size();
        vector<vector<bool>> dp(n, vector<bool>(n));
        int begin = 0, len = 1;
        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;
                }
                if (dp[i][j] && j - i + 1 > len)
                {
                    begin = i;
                    len = j - i + 1;
                }
            }
        }
        return s.substr(begin, len);
    }
};

3. 回文串分割 IV

题目链接

分析:如果暴力解题的话,i 和 j 可以把整个字符串分为3份,只需要遍历所有可能分为3份的情况直接判断是否都是回文串不就可以了。但是判断回文串需要花费时间,可以使用上面两道题的方法来判断是不是回文串

AC代码:

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;
    }
};

4. 分割回文串 ||

题目链接

  1. 状态表示

    dp[i]表示0 到 i 之间,可以把所有子串都分割为回文串的最小次数

  2. 状态转移方程

    【动态规划】回文串问题,动态规划,算法

  3. 初始化

    所需初始位最大即可

  4. 填表

    从左到右

  5. 返回值

AC代码:

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++)
            {
                if (s[i] == s[j]) isPal[i][j] = i + 1 < j ? isPal[i + 1][j - 1] : true;
            }
        }
        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];
    }
};

5. 最长回文子序列

题目链接

  1. 状态表示

    之前以某个位置为结尾来分析状态表示,如果dp[i]表示到i位置的最长回文子序列的长度来推导状态转移方程,只有长度是分析不出来状态转移方程。

    dp[i][j]表示i j 这个区间内,最长的回文子序列的长度

  2. 状态转移方程

    【动态规划】回文串问题,动态规划,算法

  3. 初始化

    无需初始化

  4. 填表

    因为需要用到 后面的值,所以填表需要从下到上,从左到右

  5. 返回值

AC代码:

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--)
        {
            for (int j = i; j < n; j++)
            {
                if (s[i] == s[j])
                {
                    dp[i][j] = i ==j ? 1 : dp[i + 1][j - 1] + 2;
                }
                else dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);
            }
        }
        return dp[0][n - 1];
    }
};

6. 让字符串成为回文串的最小插入次数

题目链接

  1. 状态表示

    dp[i][j]表示:i 到 j 这个区间内,成为回文串的最小插入次数

  2. 状态转移方程

    【动态规划】回文串问题,动态规划,算法

  3. 初始化

  4. 填表

    从下往上,从左到右

  5. 返回值

AC代码:

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

到了这里,关于【动态规划】回文串问题的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 动态规划课堂6-----回文串问题

    目录 引言: 例题1:回文子串 例题2:回文串分割IV 例题3:分割回文串II 例题4:最长回文子序列 例题5:让字符串成为回文串的最小插入次数 回文字符串  是正着读和倒过来读一样的字符串。 动态规划的回文串问题一般是把 子串 是否是回文串的信息保持在dp表里面,所以更

    2024年03月18日
    浏览(47)
  • c++--动态规划回文串问题

    1.回文子串   力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台 给定一个字符串 s ,请计算这个字符串中有多少个回文子字符串。 具有不同开始位置或结束位置的子串,即使是由相同的字符组成,也会被视作不同的子串。 示例 1: 示例 2: 分析:   2.最长回文串  力扣(

    2024年02月11日
    浏览(37)
  • leetCode 131.分割回文串 + 动态规划 + 回溯算法 + 优化 + 图解 + 笔记

    我的往期文章: leetCode 647.回文子串 动态规划 + 优化空间 / 中心扩展法 + 双指针-CSDN博客 https://blog.csdn.net/weixin_41987016/article/details/133883091?spm=1001.2014.3001.5501 leetCode 131.分割回文串 + 回溯算法 + 图解 + 笔记-CSDN博客 https://blog.csdn.net/weixin_41987016/article/details/134700907?spm=1001.2014.3001

    2024年02月05日
    浏览(52)
  • 【动态规划】【二分查找】【C++算法】730. 统计不同回文子序列

    视频算法专题 动态规划汇总 二分查找算法合集 给你一个字符串 s ,返回 s 中不同的非空回文子序列个数 。由于答案可能很大,请返回对 109 + 7 取余 的结果。 字符串的子序列可以经由字符串删除 0 个或多个字符获得。 如果一个序列与它反转后的序列一致,那么它是回文序列

    2024年01月19日
    浏览(49)
  • 算法打卡day49|动态规划篇17| Leetcode 647. 回文子串、516.最长回文子序列

    Leetcode 647. 回文子串 题目链接:647. 回文子串 大佬视频讲解:647. 回文子串视频讲解  个人思路  这道题的dp数组有点难找到关联,以至于递归关系也不好找,所以看题解吧... 解法 动态规划 动规五部曲: 1.确定dp数组(dp table)以及下标的含义 一般在定义dp数组的时候 会根据题

    2024年04月22日
    浏览(46)
  • day57|动态规划17-最长回文子串问题

    回文子串:强调连续 回文子序列:不强调连续 暴力思路:三层for循环 双指针思路: 动态规划 dp数组 dp[i][j]: 根据字符串的形式和所解决的问题确定dp数组的形式和含义。 递归公式 (分情况讨论) 2.1 如果 i j 2.2 如果 j-i 1 2.3 如果 j-i1: 此时依赖于dp[i+1][j-1]是不是一个回文子

    2024年02月09日
    浏览(40)
  • 【算法|动态规划No30】leetcode5. 最长回文子串

    个人主页:兜里有颗棉花糖 欢迎 点赞👍 收藏✨ 留言✉ 加关注💓本文由 兜里有颗棉花糖 原创 收录于专栏【手撕算法系列专栏】【LeetCode】 🍔本专栏旨在提高自己算法能力的同时,记录一下自己的学习过程,希望对大家有所帮助 🍓希望我们一起努力、成长,共同进步。

    2024年02月08日
    浏览(37)
  • 【算法题】动态规划中级阶段之最长回文子串、括号生成、跳跃游戏

    动态规划(Dynamic Programming,简称 DP)是一种解决多阶段决策过程最优化问题的方法。它是一种将复杂问题分解成重叠子问题的策略,通过维护每个子问题的最优解来推导出问题的最优解。 动态规划的主要思想是利用已求解的子问题的最优解来推导出更大问题的最优解,从而

    2024年02月12日
    浏览(43)
  • 最长回文子序列问题的原理与实现:动态规划的又一经典应用

    回文是指一个正着读和反着读都一样的字符串,比如 “aba” , “racecar” , “madam” 等。回文有许多有趣的性质和应用,比如在密码学,生物信息学,数据压缩等领域都有涉及。 那么,给定一个字符串,如何找出它的最长回文子序列呢?最长回文子序列是指从原字符串中删

    2023年04月13日
    浏览(49)
  • 【算法】力扣【动态规划,LCS】1312. 让字符串成为回文串的最少插入次数

    1312. 让字符串成为回文串的最少插入次数 本文探讨的是力扣(LeetCode)上的第1312题:让字符串成为回文串的最少插入次数。这是一道属于动态规划类别下的困难题目,通常以回文串相关的操作来衡量算法的优化和执行效率。 问题的核心是给定一个字符串 s ,你可以在任意位

    2024年01月23日
    浏览(47)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包