动态规划学习——最长回文子序列,让字符串变成回文串的最小插入次数

这篇具有很好参考价值的文章主要介绍了动态规划学习——最长回文子序列,让字符串变成回文串的最小插入次数。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

动态规划学习——最长回文子序列,让字符串变成回文串的最小插入次数,动态规划算法学习,动态规划,学习,算法,学习笔记,c++

一,最长回文串

1.题目

给你一个字符串 s ,找出其中最长的回文子序列,并返回该序列的长度。

子序列定义为:不改变剩余字符顺序的情况下,删除某些字符或者不删除任何字符形成的一个序列。

示例 1:

输入:s = "bbbab"
输出:4
解释:一个可能的最长回文子序列为 "bbbb" 。

示例 2:

输入:s = "cbbd"
输出:2
解释:一个可能的最长回文子序列为 "bb" 。

提示:

  • 1 <= s.length <= 1000
  • s 仅由小写英文字母组成

2.题目接口

class Solution {
public:
    int longestPalindromeSubseq(string s) {

    }
};

 3.解题思路及其代码

      在思考这道题时,我们先想到的可能是dp[i]来作状态转移方程,表示以第i个位置为结尾的最长回文子序列。但是,我们是不能这样定义的。因为第i个位置能不能加入到这个子序列中是要看当前子序列的开头位置的字符是否与之匹配的。

      在弄明白抛弃掉这种想法以后,我们便可以试着以区间dp的方式来解决:

1.状态表示:dp[i][j],表示在区间[i,j]的最长子序列。

2.状态转移方程:对于状态转移方程的推导需要分类讨论,分类如下:

动态规划学习——最长回文子序列,让字符串变成回文串的最小插入次数,动态规划算法学习,动态规划,学习,算法,学习笔记,c++

在第二种情况下dp[i][j]要等于在这三种情况下的最大值,又因为dp[i+1][j-1]其实是在剩下的两种情况中包含的,所以dp[i][j] = max(dp[i+1][j],dp[i][j-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][j] = dp[i+1][j]的情况,所以要从下到上初始化
        {
            for(int j = i;j<n;j++)//j>=i
            {
               if(s[i] == s[j])//第一种情况
               {
                   if(j>i) dp[i][j] = dp[i+1][j-1]+2;//j>i才能加2
                   else dp[i][j] = 1;//i == j,个数为1
               }
               else//第二种情况
               {
                   dp[i][j] = max(dp[i+1][j],dp[i][j-1]);//不用担心越界的情况,因为当j == 0时
                                                         //i一定等于0,所以会在第一种情况中处理
               }
            }
        }

       return dp[0][n-1];
    }

};

二,让字符串成为回文串的最小插入次数

1,题目

1312. 让字符串成为回文串的最少插入次数

提示

困难

218

相关企业

给你一个字符串 s ,每一次操作你都可以在字符串的任意位置插入任意字符。

请你返回让 s 成为回文串的 最少操作次数 。

「回文串」是正读和反读都相同的字符串。

示例 1:

输入:s = "zzazz"
输出:0
解释:字符串 "zzazz" 已经是回文串了,所以不需要做任何插入操作。

示例 2:

输入:s = "mbadm"
输出:2
解释:字符串可变为 "mbdadbm" 或者 "mdbabdm" 。

示例 3:

输入:s = "leetcode"
输出:5
解释:插入 5 个字符后字符串变为 "leetcodocteel" 。

提示:

  • 1 <= s.length <= 500
  • s 中所有字符都是小写字母。

2.题目接口

class Solution {
public:
    int minInsertions(string s) {

    }
};

3.解题思路及其代码

对于这种回文串问题,因为有了上面的定义状态表示的经验所以还是使用一个二维的dp表解决问题。

1.状态表示:dp[i][j]表示在[i,j]这个区间内使这个区间内的字符串成为回文串的最小插入次数。

2.状态转移方程:在这里状态转移方程还是要分类讨论,还是要看s[i],s[j]是否相等:

动态规划学习——最长回文子序列,让字符串变成回文串的最小插入次数,动态规划算法学习,动态规划,学习,算法,学习笔记,c++

在第二种情况下要取两者的较小值。

代码:

由以上思路写出代码如下:文章来源地址https://www.toymoban.com/news/detail-766773.html

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--)//有dp[i][j] = dp[i+1][j]+1的情况,所以要从下到上遍历
         {
            for(int j = i;j<n;j++)
            {
                if(s[i] == s[j])
                {
                    if(j>i) dp[i][j] = dp[i+1][j-1];//只有一个字符不用搞了
                }
                else
                {
                    dp[i][j] = min(dp[i+1][j],dp[i][j-1])+1;
                }
            }
         }

         return dp[0][n-1];

    }
};

到了这里,关于动态规划学习——最长回文子序列,让字符串变成回文串的最小插入次数的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • 剑指offer(C++)-JZ48:最长不含重复字符的子字符串(算法-动态规划)

    作者:翟天保Steven 版权声明:著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处 题目描述: 请从字符串中找出一个最长的不包含重复字符的子字符串,计算该最长子字符串的长度。 数据范围:  s.length≤40000 s.length≤40000 示例: 输入: 返回值: 说明

    2024年02月06日
    浏览(54)
  • (动态规划) 剑指 Offer 48. 最长不含重复字符的子字符串 ——【Leetcode每日一题】

    难度:中等 请从字符串中找出一个最长的不包含重复字符的子字符串,计算该最长子字符串的长度。 示例 1: 输入: “abcabcbb” 输出: 3 解释: 因为无重复字符的最长子串是 “abc”,所以其长度为 3。 示例 2: 输入: “bbbbb” 输出: 1 解释: 因为无重复字符的最长子串是 “b”,所

    2024年02月11日
    浏览(55)
  • 动态规划-最长的回文序列

    该题是lintcode上 667 · 最长的回文序列,该题的解题思路亦是参考了九章侯老师的解题思路给出。 给一字符串 s, 找出在 s 中的最长回文子序列的长度. 你可以假设 s 的最大长度为 1000. 输入: “bbbab” 输出: 4 解释: 一个可能的最长回文序列为 “bbbb” 输入: “bbbbb” 输出:

    2024年02月09日
    浏览(45)
  • 【五一创作】( 字符串) 409. 最长回文串 ——【Leetcode每日一题】

    难度:简单 给定一个包含大写字母和小写字母的字符串 s ,返回 通过这些字母构造成的 最长的回文串 。 在构造过程中,请注意 区分大小写 。比如 \\\"Aa\\\" 不能当做一个回文字符串。 示例 1: 输入:s = “abccccdd” 输出:7 解释: 我们可以构造的最长的回文串是\\\"dccaccd\\\", 它的长度是

    2024年02月01日
    浏览(53)
  • ( 动态规划) 516. 最长回文子序列 ——【Leetcode每日一题】

    难度:中等 给你一个字符串 s ,找出其中最长的回文子序列,并返回该序列的长度。 子序列定义为:不改变剩余字符顺序的情况下,删除某些字符或者不删除任何字符形成的一个序列。 示例 1: 输入:s = “bbbab” 输出:4 解释:一个可能的最长回文子序列为 “bbbb” 。 示例

    2024年02月06日
    浏览(42)
  • 每天一道leetcode:516. 最长回文子序列(动态规划&中等)

    给你一个字符串 s ,找出其中最长的回文子序列,并返回该序列的长度。 子序列定义为:不改变剩余字符顺序的情况下,删除某些字符或者不删除任何字符形成的一个序列。 1 = s.length = 1000 s 仅由小写英文字母组成 动态规划 ,使用二维dp数组记录[i,j]间的最大回文子序列长度

    2024年02月13日
    浏览(45)
  • 264.【华为OD机试真题】最长子字符串的长度(二)(动态规划DP-Java&Python&C++&JS实现)

    🚀点击这里可直接跳转到本专栏,可查阅顶置最新的华为OD机试宝典~ 本专栏所有题目均包含优质解题思路,高质量解题代码(JavaPythonC++JS分别实现),详细代码讲解,助你深入学习,深度掌握!

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

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

    2024年04月22日
    浏览(44)
  • 【算法训练-字符串 三】最长公共子串、最长公共子序列

    废话不多说,喊一句号子鼓励自己:程序员永不失业,程序员走向架构!本篇Blog的主题是【】,使用【】这个基本的数据结构来实现,这个高频题的站点是: CodeTop ,筛选条件为: 目标公司+最近一年+出现频率排序 ,由高到低的去 牛客TOP101 去找,只有两个地方都出现过才做

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

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

    2023年04月13日
    浏览(49)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包