DP:回文串模型

一、回文子串

. - 力扣(LeetCode)

 该题有3种解法

(1)中心扩展算法(在字符串章节有介绍)时间复杂度O(N^2),空间复杂度O(1)

(2)马丁车算法(专门用来解决回文串问题,但是适用返回太窄)时间复杂度O(N),空间复杂度O(N)

(3)动态规划(可以将所有回文信息都保存在dp表中)时间复杂度O(N^2),空间复杂度O(N^2)

这边重点介绍动态规划的做法。

算法原理:

1、状态表示(经验+题目要求)

dp[i][j]表示s字符串[i,j]的子串是否是回文串(i<=j)只需处理右上区即可

 2、状态转移方程

dp[i][j]:  

(1)s[i]!=s[j]——>false

(2)s[i]==s[j]——>

      i==j  true 

      i+1==j   true

      dp[i+1][j-1]

3、初始化

无需初始化

4、填表顺序

dp[i][j]会用到dp[i+1][j-1],所以必须要从下往上填 , 左右顺序不重要

5、返回值

dp表中true的个数

class Solution {
public:
    int countSubstrings(string s) {
      //动态规划的做法
      int ret=0;
      //s[i]==s[j]  1、i==j  2、i+1==j  3、dp[i+1][j-1]?
      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]) ret+=dp[i][j]=i+1<j?dp[i+1][j-1]:true;
      return ret;
    }
};

 二、最长回文子串

. - 力扣(LeetCode)

算法原理:

1、状态表示(经验+题目要求)

dp[i][j]表示s字符串[i,j]的子串是否是回文串(i<=j)只需处理右上区即可

 2、状态转移方程

dp[i][j]:  

(1)s[i]!=s[j]——>false

(2)s[i]==s[j]——>

      i==j  true 

      i+1==j   true

      dp[i+1][j-1]

3、初始化

无需初始化

4、填表顺序

dp[i][j]会用到dp[i+1][j-1],所以必须要从下往上填 , 左右顺序不重要

5、返回值

dp表中为true以及长度最大的子串的起始位置和长度

class Solution {
public:
    string longestPalindrome(string s) {
    //动态规划的思想
    int begin=0,len=1;//帮助我们返回结果
    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;
                if(dp[i][j]&&len<j-i+1) 
                {
                    begin=i;
                    len=j-i+1;
                }
            }  
        }
    return s.substr(begin,len);
    }
};

三、分割回文子串I

. - 力扣(LeetCode)

解法1:动归预处理+回溯

class Solution {
public:
   //动归预处理+回溯
    vector<vector<bool>> dp;//dp预处理
    vector<vector<string>> ret;//记录返回的结果
    vector<string> path;//记录路径的结果
    int n;
    vector<vector<string>> partition(string s) {
       //dp预处理
       n=s.size();
       dp.resize(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;
        //将dp数组交给dfs去处理
        dfs(s,0);
        return ret;
    }
    void dfs(string&s,int i)
    {
        if(i==n) 
        {
            ret.push_back(path);
            return;
        }
        for(int j=i;j<n;++j)
            if(dp[i][j])
            {
                path.emplace_back(s.substr(i,j-i+1));
                dfs(s,j+1);
                path.pop_back();
            }
    }
};

 解法2:回溯+记忆化搜索

class Solution {
public:
//回溯+记忆化搜索
    vector<vector<int>> f;//记忆化数组  0表示未搜索,1表示回文,-1表示不回文
    vector<vector<string>> ret;//记录返回的结果
    vector<string> path;//记录路径的结果
    int n;
    vector<vector<string>> partition(string s) {
      n=s.size();
      f.resize(n,vector<int>(n));
      //交给dfs帮助我们解决
      dfs(s,0);
      return ret;
    }
    void dfs(const string&s,int i)
    {
        if(i==n) 
        {
            ret.emplace_back(path);
            return;
        }
        for(int j=i;j<n;++j)
          if(ispal(s,i,j))
        {
            path.emplace_back(s.substr(i,j-i+1));
            dfs(s,j+1);
            path.pop_back();
        }
    }
    bool ispal(const string&s,int i,int j) //判断i->j是否回文
    {
       //先看看备忘录
       if(f[i][j]) return f[i][j];
       if(s[i]!=s[j]) return f[i][j]=false;
       else return f[i][j]=i+1<j?ispal(s,i+1,j-1):true;
    }
};

四、分割回文子串II

. - 力扣(LeetCode)

算法原理:

1、状态表示(经验+题目要求)

dp[i]表示s字符串[0,i]区间上的最长子串的最小分割次数

 2、状态转移方程

dp[i]:  

(1)0-i回文——>0

(2)0-i不是回文——>j-i是否回文——>min(dp[i],dp[j-1]+1)

3、初始化

都初始化为整型最大值,否则最后dp表里都是0会影响结果

4、填表顺序

dp[i][j]会用到dp[i+1][j-1],所以必须要从下往上填 , 左右顺序不重要

5、返回值

dp[n-1]

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);//j代表最后一个回文串的起始位置
         return dp[n-1];
    }
};

五、分割回文子串III(经典)

. - 力扣(LeetCode)

算法原理:

1、状态表示(经验+题目要求)

dp[i][j]表示对于字符串的前i个字符,将他分割成j个子串,所需修改的最少字符数

 2、状态转移方程

int cost(string&s,int l,int r) 表示从s的i-j位置,变成回文串所需要的最小修改次数

dp[i][j]:  

(1)j==1(没有分割)  cost(s,0,i-1)

(2)j>1——>min(dp[i][j],dp[m][j-1]+cost(s,m,i-1))

3、初始化

初始化成INT_MAX 确保不影响最终结果 dp[0][0]=0 确保不影响结果

4、填表顺序

上到下,左到右

5、返回值

dp[n][k]

class Solution {
public:
    int palindromePartition(string s, int k) {
    //dp[i][j]表示对于字符串的前i个字符,将他分割成j个子串,所需修改的最少字符数
    int n=s.size();
    vector<vector<int>> dp(n+1,vector<int>(k+1,INT_MAX));
    dp[0][0]=0;
    for(int i=1;i<=n;++i)
      for(int j=1;j<=min(k,i);++j)
         if(j==1) dp[i][j]=cost(s,0,i-1);
         else 
            for(int m=j-1;m<i;++m) dp[i][j]=min(dp[i][j],dp[m][j-1]+cost(s,m,i-1));
            //找前面的状态 0->i  分成j个
            //dp0->m+ cost m->i

       return dp[n][k];//0->n  k
    }

    int cost(string&s,int l,int r)
    {
        int ret=0;
        for(int i=l,j=r;i<j;++i,--j)
         if(s[i]!=s[j]) ++ret;//需要修改一个才能成为回文
       return ret;
    }
};

六、分割回文串IV

 . - 力扣(LeetCode)

算法原理:

1、状态表示(经验+题目要求)

dp[i][j]表示s字符串[i,j]的子串是否是回文串(i<=j)只需处理右上区即可

 2、状态转移方程

dp[i][j]:  

(1)s[i]!=s[j]——>false

(2)s[i]==s[j]——>

      i==j  true 

      i+1==j   true

      dp[i+1][j-1]

3、初始化

无需初始化

4、填表顺序

dp[i][j]会用到dp[i+1][j-1],所以必须要从下往上填 , 左右顺序不重要

5、返回值

第二次枚举,先固定第一个位置,然后固定第二个位置,看看由两个位置分割出来的三个区域是否都为true

class Solution {
public:
    bool checkPartitioning(string s) {
       //将结果存到dp表中
    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;
     //第二次枚举 先固定第一个,然后固定第二个,然后看看3个是不是都是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;
    }
};

七、不重叠回文子字符串的最大数目

. - 力扣(LeetCode)

class Solution {
public:
    int maxPalindromes(string s, int k) {
        //dp[i]表示0->i中的不重叠回文子字符串的最大数目
        int n=s.size();
        vector<int> dp(n+1);
        //如果s[i]不在回文串中 dp[i+1]=dp[i]
        //如果s[r]在回文串中,采用中心扩展,l->r是回文子串,且r-l+1>=k 有dp[i]=max(dp[i],dp[l-1]+1)
        for(int i=0;i<n*2-1;++i)
        {
            //两边到中间不适合判断长度,应该从中间到两边
          int l=i/2,r=l+i%2; //中心扩展判断是否回文
          dp[l+1]=max(dp[l],dp[l+1]);
          for(;l>=0&&r<n&&s[l]==s[r];--l,++r)
             if(r-l+1>=k)
             {
                dp[r+1]=max(dp[r+1],dp[l]+1);
                break;
             }
        }
        return dp[n];
    }
};

八、最长回文子序列

. - 力扣(LeetCode)

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]表示i-j区间内所有子序列中,最长回文子序列的长度
          dp[i][i]=1;
          for(int j=i+1;j<n;++j)
            if(s[i]==s[j]) dp[i][j]=dp[i+1][j-1]+2; //i+1=j的情况可以不用考虑 
            //虽然会出现用不到的格子,但是里面是0所以不会影响计算结果
            else dp[i][j]=max(dp[i+1][j],dp[i][j-1]);
       }
       return dp[0][n-1];
    }
};

算法原理:

1、状态表示(经验+题目要求)

dp[i][j]表示s字符串[i,j]所有子序列中的最长子序列的长度

 2、状态转移方程

dp[i][j]:  

(1)s[i]!=s[j]——>max(dp[i,j-1],dp[i+1][j])

(2)s[i]==s[j]——>

      i==j  1

      i+1==j   2

      dp[i+1][j-1]+2

3、初始化

初始化为0  dp[i][i]=1

4、填表顺序

上到下,左到右

5、返回值

dp[0][n-1]

九、让字符串成为回文串的最小插入次数

. - 力扣(LeetCode)

算法原理:

1、状态表示(经验+题目要求)

dp[i][j]表示s字符串[i,j]子串,使他成为回文子串的最小插入次数

 2、状态转移方程

dp[i][j]:  

(1)s[i]!=s[j]——>min(dp[i,j-1],dp[i+1][j])+1

(2)s[i]==s[j]——>

      i==j  0

      i+1==j   0

      dp[i+1][j-1]

3、初始化

初始化为0 

4、填表顺序

下往上,左到右

5、返回值

dp[0][n-1]

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+1;j<n;++j)
           if(s[i]==s[j]) dp[i][j]=dp[i+1][j-1];
           else dp[i][j]=min(dp[i][j-1],dp[i+1][j])+1;
       return dp[0][n-1];
    }
};

 

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/695322.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

(二)深度学习基础练习题(54道选择题)

本文整理了深度学习基础知识相关的练习题&#xff0c;共54道&#xff0c;适用于想巩固深度学习基础的同学。来源&#xff1a;如荷学数据科学题库&#xff08;技术专项-深度学习&#xff09;。 1&#xff09; 2&#xff09; 3&#xff09; 4&#xff09; 5&#xff09; 6&#…

【iOS】UI学习——登陆界面案例、照片墙案例

文章目录 登陆界面案例照片墙案例 登陆界面案例 这里通过一个登陆界面来复习一下前面学习的内容。 先在接口部分定义两个UILabel、两个UITextField、两个UIButton按键&#xff1a; #import <UIKit/UIKit.h>interface ViewController : UIViewController {UILabel* _lb…

零基础直接上手java跨平台桌面程序,使用javafx(二)可视化开发Scene Builder

我们只做实用的东西&#xff0c;不学习任何理论&#xff0c;如果你想学习理论&#xff0c;请去买几大本书&#xff0c;慢慢学去。 NetBeans有可视化工具&#xff0c;但是IntelliJ IDEA对于javafx,默认是没有可视化工具的。习惯用vs的朋友觉得&#xff0c;写界面还要是有一个布局…

【双指针算法】原地处理数组的双指针算法思想

移动零 题目中已经明确表示不能重新创建数组来辅助解题&#xff0c;因此只能对数组进行原地操作&#xff0c;即双指针算法思想。 算法思想&#xff1a; 题目要求我们将非0元素放在数组的左边&#xff0c;0元素放在数组的右边&#xff0c;同时保持非0元素的相对位置。 这种对…

归并排序——逆序数对的统计

逆序数对的统计 题目描述 运行代码 #include <iostream> using namespace std; #define LL long long const int N 1e5 5; int a[N], tmp[N]; LL merge_sort(int q[], int l, int r) {if (l > r)return 0; int mid l r >> 1; LL res merge_sort(q, l,…

QT-轻量级的笔记软件MyNote

MyNote v2.0 一个轻量级的笔记软件&#x1f4d4; Github项目地址: https://github.com/chandlerye/MyNote/tree/main 应用简介 MyNote v2.0 是一款个人笔记管理软件&#xff0c;没有复杂的功能&#xff0c;旨在提供便捷的笔记记录、管理以及云同步功能。基于Qt 6.6.3 个人开…

【Qt】Qt常见的数据类型

思维导图 学习目标 一、基础类型 因为Qt是一个C的框架&#xff0c;因此C的语法和数据类型在Qt中都是被支持的&#xff0c;但是Qt中也是定义了一些属于自己的数据类型&#xff0c;不过&#xff0c;好多数据类型都是对C的数据类型进行封装&#xff0c;下面来简要介绍一下这些基…

kafka集成SpringBoot api编写教程

1.新建项目 用的idea是20222.1.3版本&#xff0c;没有Spring Initializr 插件&#xff0c;不能直接创建springboot项目 可以在以下网址创建项目&#xff0c;下载后解压&#xff0c;然后用idea打开项目即可 1.1 在 https://start.spring.io/ 上创建项目 1.2上传到linux&#x…

第十四周 6.4 内部类部分知识点

一、理解 1.定义在一个类内部的类称为内部类 2.语法: class 类名{ class 类名{} } 3.内部类编译之后生成独立的.class文件&#xff0c;文件命名为:外部类类名$内部类的类名.class 4.内部类分类:成员内部类、静…

Layui弹框中设置输入框自动获取焦点无效/Layui设置Input框自动获取焦点无效,怎么办?

1、问题概述? 有时候为了用户体验,期望当弹框打开的时候,指定的输入框能自动的获取焦点,用户就可以直接输入了。提升了用户体验。但有时候设置的时候没有效果。 2、正常的设置自动获取焦点方式 【input框设置方式】 使用关键字autofocus <input type="text&quo…

OPenCV的重要结构体Mat

一 Mat Mat是什么&#xff1f; Mat有什么好处&#xff1f; class CV_EXPORTS Mat{ public: ... int dims;//维数 int rows,cols;//行列数 uchar *data;//存储数据的指针 int *refcount;//引用计数 ...};二 Mat属性 三 Mat拷贝 1 Mat浅拷贝 Mat A Aimread(file,IMREAD_COLOR) …

Java入门教程上

常见的cmd命令 类 class 字面量 数据类型 输入 public static void main(String[] args) {Scanner anew Scanner(System.in);int na.nextInt();int ma.nextInt();System.out.println(mn);} } 算数运算符 package wclg;public class test {public static void main(String[] ar…

网络安全难学吗?2024该怎么系统学习网络安全?

学习网络安全需要循序渐进&#xff0c;由浅入深。很多人对网络安全进行了解以后&#xff0c;就打算开始学习网络安全&#xff0c;但是又不知道怎么去系统的学习。 网络安全本身的知识不难&#xff0c;但需要学习的内容有很多&#xff0c;其中包括Linux、数据库、渗透测试、等保…

【算法专题--链表】环形链表--高频面试题(图文详解,小白一看就会!!)

目录 一、前言 二、什么是环形链表&#xff1f; &#x1f95d; 环形链表的概念详解 &#x1f347; 环形链表的特点 &#x1f34d;环形链表的延申问题 三、高频面试题 ✨环形链表 ✨环形链表II ✨环形链表的环长 四、总结 五、共勉 一、前言 环形链表&#xff0c;可以说是…

单臂路由的配置(思科、华为)

#交换设备 不同vlan属于不同广播域&#xff0c;不能互相通信&#xff0c;他们配置的是不同网段的IP地址&#xff0c;针对不同网段的IP地址进行通信&#xff0c;就需要用到路由技术 实现不同vlan之间的通信技术有两种 单臂路由三层交换 单臂路由 一、思科设备的单臂路由配…

Understanding Diffusion Objectives as the ELBO with Simple Data Augmentation

Understanding Diffusion Objectives as the ELBO with Simple Data Augmentation 引言 本文前作 VDM 已经推导出了扩散模型可以将优化 ELBO 作为目标函数。然而现在 FID &#xff08;也就是感知质量&#xff09;最好的模型还是用的其他目标函数&#xff08;如 DDPM 的噪声预…

矩阵LU分解的应用

矩阵LU分解在机器学习和深度学习中的应用广泛&#xff0c;主要用于解决以下问题&#xff1a; 线性方程组求解&#xff1a;LU分解可以有效地解决线性方程组&#xff0c;这在训练模型时非常有用。矩阵求逆&#xff1a;在一些机器学习算法中&#xff0c;需要进行矩阵求逆操作&…

二维鱼游CFD代码

最近学了会Julia&#xff0c;参考了原作者的shark&#xff0c;做一下基于airfoils 2D的鱼游&#xff0c;暂时没想好有什么需要深入研究的&#xff0c;代码公开如下&#xff1a; 鱼身是naca0016&#xff0c;然后一些参数可以参考我以前发的论文。 using WaterLily, StaticArra…

46.django - 多语言配置

1.Django 多语言基础知识 多语言站点可以让不同语言的用户更好地使用和理解网站内容&#xff0c;提升用户体验和覆盖范围。为了实现多语言功能&#xff0c;我们将使用Django内置的国际化和本地化支持。我收集了一些知识点整理在这一部分&#xff0c;感兴趣的可以看看。直接跳过…

k8s面试题大全,保姆级的攻略哦(三)

目录 1、简述ETCD及其特点? 2、简述ETCD适应的场景? 3、简述什么是Kubernetes? 4、简述Kubernetes和Docker的关系? 5、简述Kubernetes中什么是Minikube、Kubectl、Kubelet? 6、简述Kubernetes常见的部署方式? 7、简述Kubernetes如何实现集群管理? 8、简述Kubern…