动态规划--回文串问题

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

一)回文子串:

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

思路1:暴力枚举:

for(int i=0;i<array.length;i++)

for(int j=i;j<array.length;j++)

我们的中心思路就是枚举出所有的子字符串,然后进行判断所有的子串是否是回文串

每一次我们固定i位置,j向后走,就成功枚举出了以i位置为起点的所有回文字串的情况,将i进行++,然后再让j从i位置进行++

思路2:中心扩散:

如果以单个字符为中心向两边进行中心扩展,那么最终扩展完成之后的回文串长度都是奇数个,如果以两个字符为中心向两边进行中心扩散,那么最终扩展完成之后的回文串的长度都是偶数个,这两种方法相当于是枚举了所有的子串

class Solution {
    public int countSubstrings(String s) {
        char[] array=s.toCharArray();
        int ret=0;
        for(int i=0;i<s.length();i++){
            ret+=check(array,i,i);
            ret+=check(array,i,i+1);
        }
      return ret;
    }
    public int check(char[] array,int left,int right){
        int count=0;
        while(left>=0&&right<array.length&&array[left]==array[right]){
            left--;
            right++;
            count++;
        }
    return count;
    }
}

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

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

思路3:动态规划

回文串问题是用动态规划解决可以进行判断能够将所有的子串是否是回文的信息,保存在dp表里面,首先进行考虑的是我们的状态标识该如何找到所有的子串

dp[i][j]表示以i位置为起点,j位置为中点的子串,是否是回文串,横坐标表示起始位置,纵坐标表示结束位置

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

因为i是小于j的, 所以我们的dp表只会使用到对角线以及上三角所在的部分(i>=j)

3.1)如果array[i]!=array[j]那么从i位置到j位置的这段字符串,一定不是回文串

3.2)如果array[i]==array[j],又是分成三种情况:

if(i==j) dp[i][j]=true

else if(i+1==j) dp[i][j]=true

else dp[i][j]=dp[i+1][j-1]

进行填表的时候只是会用到上三角的值,从下向上填表,从左向右进行填表

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

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

dp[i][j]是以i位置和j位置元素为结尾的字符串是否是回文串,但是如果是i==j的情况,或者是i+1==j的情况,如果还是使用状态转移方程dp[i][j]=dp[i+1][j-1]这种方法来搞的话,此时j下标就会跳到i下标的前面,此时就和我们的状态表示发生了冲突

初始化:不用初始化

填表顺序:从下向上,每一行,因为当进行填写当前行的时候要使用到下一行的值

返回值:返回的是dp表中true的个数

class Solution {
    public int countSubstrings(String s) {
        int count=0;
        char[] array=s.toCharArray();
        boolean[][] dp=new boolean[array.length][array.length];
        for(int i=array.length-1;i>=0;i--){
            for(int j=i;j<array.length;j++){//保证j在i后面
                if(array[i]==array[j]){
                    dp[i][j]=i+1==j||i==j?true:dp[i+1][j-1];
                }else{
                   dp[i][j]=false;
                }
                if(dp[i][j]==true) count++;
            }
        }
    return count;

    }
}

二)最长回文子串:

先进行判断这个子串是否回文,然后再次进行统计所有子串的个数

填表顺序:用当前位置的值需要使用到下一行位置的值,所以需要从下向上进行填表即可

返回值:dp值是true的情况下,返回长度最大的字串的起始位置以及长度

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

class Solution {
    public String longestPalindrome(String s) {
        char[] array=s.toCharArray();
        int maxlen=-1;
        String maxString="";
        boolean[][] dp=new boolean[array.length][array.length];
        for(int i=array.length-1;i>=0;i--){
            for(int j=i;j<array.length;j++){
                if(array[i]==array[j]){
                    dp[i][j]=(j==i+1||i==j)?true:dp[i+1][j-1];
            if(j-i+1>=maxlen){
                    maxString=s.substring(i,j+1);
                    maxlen=j-i+1;
            }
                }else{
                    dp[i][j]=false;
                }
            }
        }
    return maxString;
    }
}

三)回文串分割:

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

暴力枚举:将所有的三元组字符串给进行枚举一下,将所有的分割出来的三个字符串给进行枚举一下,只要枚举完成,只需要将三个字符串都进行判断一下是否是回文即可

我们将整个字符串分割成三部分:

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

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

我们设i是第一个字符串的起始位置,j表示第二个字符串的终止位置,可以枚举第二个字符串的起始位置和终止位置

class Solution {
    public boolean checkPartitioning(String s) {
//1.利用dp来进行检查一下所有的子串是否回文
        char[] array=s.toCharArray();
        boolean[][] dp=new boolean[array.length][array.length];
        for(int i=array.length-1;i>=0;i--){
            for(int j=i;j<array.length;j++){
                if(array[i]==array[j]){
                    dp[i][j]=i+1==j||i==j?true:dp[i+1][j-1];
                }else{
                   dp[i][j]=false;
                }
            }
        }
//2.枚举第二个字符串的所有的起始位置和终止位置
    for(int i=1;i<array.length;i++){//既然是枚举第二个字符串,那么前一个字符串必须得存在
        for(int j=i;j<array.length-1;j++){//至少要给最后一个字符串枚举
    if(dp[0][i-1]==true&&dp[i][j]==true&&dp[j+1][array.length-1]==true){
                return true;
            }
        }
    }
 return false;
    }
}

四)分割回文串:

132. 分割回文串 II - 力扣(LeetCode)

1)定义一个状态表示:

dp[i]表示以字符串i为结尾最长的子串的最少分割次数

2)根据状态标识推导状态转移方程

1)快速确定某一个字符串的子串是否是回文串

2)可以创建一个二维dp表,将所有的子串是否是回文的信息,保存到hash表里面

j==0的时候,0-i位置的字符传是否是回文子串已经考虑过了

j==i的时候,起始位置就是最后一个字符

3)如果0-i区间内的字符串是一个回文串,就不需要进行切割,那么我们就设j为最后一个字符串的起始字符,如果0-i区间内的字符串不是回文串,我们就想一下如果0-j区间内的字符串能够被分割成一个回文串况且有最小分割次数,况且dp[j][i]是一个回文串,那么此时dp[i]=dp[j-1]+1;

4)j>=0&&j<=i,如果j==0的话,那么那么表示j是第一个字符串的起始位置,已经被dp[i]考虑过了,所以j的取值范围就是j>0&&j<=i

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

 如果判断f[0][i]的逻辑写到循环里面

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

dp[i]=Math.min(dp[j-1]+1,dp[i])为了使我们再进行第一次进行比较的时候dp[i]的之不要去干扰我们第一次比较的结果,可以让dp[i]全部初始化成Integer.MIN_VALUE

在进行填写dp[i]的时候,至少要保证dp[j-1]已经被初始化完成了,所以填表顺序是从左向右

上面代码块这么写会导致进行计算f[0][0]的时候计算错误回文串问题,动态规划,算法

    public int minCut(String s) {
//1.先将这个字符串进行预处理,将字符串中每一个子字符串是否是回文串的信息存放到一个二维的dp表里面
        char[] array=s.toCharArray();
        boolean[][] f=new boolean[array.length][array.length];
        int[] g=new int[array.length];
        for(int i=array.length-1;i>=0;i--){
            for(int j=i;j<array.length;j++){
                if(array[i]==array[j]){
                    f[i][j]=i==j||i+1==j?true:f[i+1][j-1];
                }else{
                    f[i][j]=false;
                }
            }
        }
//2.然后再次进行字符串拆分
    for(int i=0;i<array.length;i++) 
    {
        g[i]=Integer.MAX_VALUE;
    }
   // System.out.println(Arrays.deepToString(f));
    for(int i=0;i<array.length;i++){
        for(int j=1;j<=i;j++){
            //1.首先判断0-i位置是否是回文子串
             if(f[0][i]==true) g[i]=0;
             else if(f[j][i]==true){
                g[i]=Math.min(g[i],g[j-1]+1);
        }
     }
    }
 return g[array.length-1];
    
}

 五)最长回文子序列

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

一)定义一个状态表示:

1)以i位置元素为结尾的所有子序列中最长的回文子序列的长度,如果这样定义状态标识,根本推不出状态转移方程,如果以i位置为结尾,势必就会使用到i-1,i-2等等位置的dp值来更新当前i位置的dp值,假设我们就举一个例子,dp[i-3]表示以i-3位置为结尾的最长回文子序列的长度,但是我只是知道以i-3元素为结尾的回文子序列的长度,我连i位置的元素是否可以和i-3位置的元素是否能够构成回文子序列都不知道,请问我该如何更新dp[i]的值呢?是永远无法更新出最长回文子序列的长度,首先得知道是否能够成回文子序列?根本判断不出来,根本不能由前面的状态来推导出dp[i]的值,从下图所示可以看出,从[i,j]这段区间内最长回文子序列的长度可以推导出[i+1,j+1]这段区间内最长回文子序列的长度

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

 二)根据状态标识推到状态转移方程

根据最后一个位置推导问题(i<=j)

1)dp[i][j]是以i位置元素为起点,j位置元素为终点的最长回文子序列

2)如果i位置的元素等于j位置的元素,此时i==j,此时最长回文子序列就是1,如果i+1=j,说明此时i和j两个位置的元素是相邻的,此时最长回文子序列就是2,如果i位置和j位置中间包含多个元素,那么dp[i][j]=dp[i+1][j-1],最长回文子序列一定是包含以ij位置为结尾的

3)如果i位置元素和j未知元素不相等,那么dp[i][j]最长回文子序列不可能是同时起点是i,终点是j,那么此时就去i+1到j和i到j-1去找回文子序列的最大值

4)补充:为什么要考虑i==j和i+1==j的情况呢?就是为了让状态转移方程满足dp[i][j]的含义

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

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

三)初始化,填表顺序,返回值 

初始化:我们在进行初始化的时候只会使用到对角线以及对角线以上的值

1)当我们进行填写第一个三角格子的时候,dp[i][j-1]可能会发生越界,此时i=0,j=0

2)当进行填写最下面的圆圈的时候,dp[i+1][j]可能会发生越界,此时i==j==n,但是这种情况我们在上面已经考虑过了,所以不需要进行初始化

3)正常来说,除了这两个位置,这个dp值只会依赖左边的值和下面的值,都不会发生越界

所以越界的情况都已经在dp表中考虑过了,所以我们就不需要进行初始化了

4)从下向上进行填表,每一行从左向右

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

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

填表顺序当进行填写dp表的时候,进行填写到dp[i][j]的时候,需要dp[i+1][j]的值,需要使用到下一行的值和dp[i][j-1]需要用到左边的值,所以填表顺序就是从下向上,从左向右

返回值:返回dp[0][array.length-1]里面的值

class Solution {
    public int longestPalindromeSubseq(String s) {
      char[] array=s.toCharArray();
//1.dp[i][j]表示以i位置为开头,j位置元素为结尾最长回文子序列的长度
      int[][] dp=new int[array.length][array.length];
//2.进行填写dp表,从下向上进行填表
      for(int i=array.length-1;i>=0;i--){
          for(int j=i;j<array.length;j++){
             if(array[i]==array[j]){
                 if(i==j) dp[i][j]=1;
                 else if(i+1==j) dp[i][j]=2;
                 else dp[i][j]=dp[i+1][j-1]+2;
             }else{
                 dp[i][j]=Math.max(dp[i+1][j],dp[i][j-1]);
             }
          }
      }
    return dp[0][array.length-1];
    }
}

六)让字符串成为回文串的最少插入次数

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

做回文串的题的时候,状态表示都是选取一段区间来进行研究问题

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

默认情况下就是i<=j的 

一)定义一个状态表示

dp[i][j]表示s字符串内[i,j]这段区间内的子字符串使它成为回文串的最小插入次数

二)根据状态表示推导状态转移方程

从i和j位置根据最近的一步划分问题,当i==j的时候,我们只需要找到i-1,j-1字符串成为回文串的最小插入次数即可

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

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

class Solution {
    public int minInsertions(String s) {
    char[] array=s.toCharArray();
    int[][] dp=new int[array.length][array.length];
//1.dp[i][j]表示以i位置为起点,j位置为终点得是这段区间成为回文串得最小插入次数
 for(int i=array.length-1;i>=0;i--){
     for(int j=i;j<array.length;j++){
         if(array[i]==array[j]){
             if(i==j) dp[i][j]=0;
             else if(i+1==j) dp[i][j]=0;
             else dp[i][j]=dp[i+1][j-1]; 
         }else{
             dp[i][j]=Math.min(dp[i+1][j]+1,dp[i][j-1]+1);
         }
     }
 }
   return dp[0][array.length-1];
    }
}

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

 文章来源地址https://www.toymoban.com/news/detail-855533.html

到了这里,关于动态规划--回文串问题的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索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

领红包