IT数码 购物 网址 头条 软件 日历 阅读 图书馆
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓ 		图片批量下载器
↓批量下载图片,美女图库↓ 		图片自动播放器
↓图片自动播放器↓ 		一键清除垃圾
↓轻轻一点,清除系统垃圾↓
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁
 
   -> 数据结构与算法 -> 字符串DP总结 -> 正文阅读

[数据结构与算法]字符串DP总结

字符串DP题型复盘


前言：
字符串DP大多数题型为用最小或最大的操作步数，使原串变为新串，因此大多数使用区间DP来解决，部分会进行区间DP优化，下边是一些常见题型。

一、回文字符串多维度变形

1.求字符串中最长回文子序列长度

这是一个区间DP模板题了，代码很容易看懂，这里不在赘述

1.最长回文子序列—区间DP

题目链接

class Solution {
public:
    int longestPalindromeSubseq(string s) {
        int n=s.size();
        s=" "+s;
        vector<vector<int>>f(n+1,vector<int>(n+1));
        for(int len=1;len<=n;len++)
            for(int i=1;i+len-1<=n;i++)
            {
                int j=i+len-1;
                if(i==j)f[i][i]=1;
                else 
                {
                    f[i][j]=max(f[i+1][j],f[i][j-1]);
                    if(s[i]==s[j])f[i][j]=max(f[i+1][j-1]+2,f[i][j]);
                }
            }
        return f[1][n];
    }
};

2.求字符串中最长回文子串长度

1.最长回文子串—区间DP

题目链接

这题易错点在于不能像大多数区间dp一样直接 l e n = 1 len=1 len=1时使 f [ i ] [ j ] = 1 f[i][j]=1 f[i][j]=1
注意要特判 l e n = 2 且 s [ i ] = s [ j ] len=2且s[i]=s[j] len=2且s[i]=s[j]的情况

class Solution {
public:
    int getLongestPalindrome(string s) {
        int n=s.size();
        s=" "+s;
        int res=0;
        vector<vector<int>>f(n+1,vector<int>(n+1));
        for(int len=1;len<=n;len++)
            for(int i=1;i+len-1<=n;i++)
            {
                int j=i+len-1;
                if(s[i]==s[j])
                {
                    if(len<=3)f[i][j]=true;
                    else f[i][j]=f[i+1][j-1];
                }
                else f[i][j]=false;
                if(f[i][j])res=max(res,j-i+1);
            }
        return res;
    }
};

2.小A的回文串—区间DP

题目链接

升级版，加了一个常见的循环处理

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
using namespace std;
const int N=5005;
bool f[2*N][2*N];
int main()
{
    string s;
    cin>>s;
    int n=s.size();
    s+=s;
    s=" "+s;
    int res=0;
    for(int len=1;len<=n;len++)
    {
        for(int i=1;i+len-1<=2*n;i++)
        {
            int j=i+len-1;
            if(s[i]==s[j])
            {
                if(j-i<3)f[i][j]=true;
                else f[i][j]=f[i+1][j-1];
            }
            else f[i][j]=false;
            if(f[i][j])res=max(res,j-i+1);
        }
    }
    cout<<res<<endl;
}

3.无权值回文字符串最值问题

1.Palindrome—LCS优化

题目链接

MLE写法：（区间DP）

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=5010;
int f[N][N];
int main()
{
    int n;
    string s;
    cin>>n;
    cin>>s;
    s=" "+s;
    for(int len=1;len<=n;len++)
    {
        for(int i=1;i+len-1<=n;i++)
        {
            int j=i+len-1;
            if(len==1)f[i][j]=0;
            else if(s[i]==s[j])
            {
                if(len==2)f[i][j]=0;
                else f[i][j]=f[i+1][j-1];
            }
            else
            {
                f[i][j]=min(f[i+1][j],f[i][j-1])+1;
            }
        }
    }
    cout<<f[1][n]<<endl;
}

滚动数组优化AC写法（这里需要用上一个数学公式）
r e s = n ? L C S res=n-LCS res=n?LCS

因为字符串和它的反向字符串的最大公共子序列的长度LCS，就等同于在原串中有LCS个字符是对应相等的。答案就是那些对应不相等的在对应位置添加相同的字符。

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=5010;
int f[2][N]={0};
int main()
{
	int n;
	cin>>n;
    string a,b;
    cin>>b;a=b;
    reverse(b.begin(),b.end());
    a=" "+a;
    b=" "+b;
    for(int i=1;i<=n;i++)
    {
    	for(int j=1;j<=n;j++)
    	{
    		f[i&1][j]=max(f[i-1&1][j],f[i&1][j-1]);
    		if(a[i]==b[j])f[i&1][j]=max(f[i&1][j],f[i-1&1][j-1]+1);
		}
	}
	cout<<n-f[n&1][n]<<endl;
}

4、有权值回文字符串最值问题

1.Cheapest Palindrome—区间dp

题目链接

d[i][j]:从i到j为回文串花费的最小
状态转移方程：
当 s [ i ] = s [ j ] s[i]=s[j] s[i]=s[j]时：

d [ i ] [ j ] = d [ i + 1 ] [ j ? 1 ] d[i][j]=d[i+1][j-1] d[i][j]=d[i+1][j?1]

否则

d [ i ] [ j ] = m i n ( d [ i ] [ j ? 1 ] + a d d [ s [ j ] ] , d [ i + 1 ] [ j ] + a d d [ s [ i ] ] , d e l [ s [ i ] ] + d [ i + 1 ] [ j ] , d e l [ s [ j ] ] + d [ i ] [ j ? 1 ] ) d[i][j]=min(d[i][j-1]+add[s[j]],d[i+1][j]+add[s[i]],del[s[i]]+d[i+1][j],del[s[j]]+d[i][j-1]) d[i][j]=min(d[i][j?1]+add[s[j]],d[i+1][j]+add[s[i]],del[s[i]]+d[i+1][j],del[s[j]]+d[i][j?1])

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
const int N = 2010;
int f[N][N];
int n,m;
int add[N],del[N];
int main()
{
    cin>>n>>m;
    string s;
    cin>>s;s=" "+s;
    char op[2];
    int x,y;
    for(int i=0;i<n;i++)
    {
    	cin>>op;
    	cin>>x>>y;
    	add[op[0]-'a']=x;
    	del[op[0]-'a']=y;
	}
	memset(f,0x3f,sizeof f);
	f[0][0]=0;
	for(int len=1;len<=m;len++)
	{
		for(int i=1;i+len-1<=m;i++)
		{
			int j=i+len-1;
			if(s[i]==s[j])
			{
				if(len<=2)f[i][j]=0;
				else f[i][j]=f[i+1][j-1];
			}
			else
			{
				int x=min(f[i+1][j]+add[s[i]-'a'],f[i][j-1]+add[s[j]-'a']);
				int y=min(f[i+1][j]+del[s[i]-'a'],f[i][j-1]+del[s[j]-'a']);
				f[i][j]=min(x,y);
			}
		}
	}
	cout<<f[1][m]<<endl;
}

5.合并回文子串

1.合并回文子串—区间DP

题目链接

相当于在最长回文子串的基础上扩展二维

详细题解入口：传送门

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
const int N=110;
void solve()
{
    bool f[N][N][N][N];
    int res=0;
    string a,b;
    cin>>a>>b;
    int n=a.size(),m=b.size();
    a=" "+a,b=" "+b;
    for(int len1=0;len1<=n;len1++)
    {
        for(int len2=0;len2<=m;len2++)
        {
            for(int i=1;i+len1-1<=n;i++)
            {
                for(int k=1;k+len2-1<=m;k++)
                {
                    int j=i+len1-1,l=k+len2-1;
                    if(len1+len2<=1)f[i][j][k][l]=1;
                    else
                    {
                        bool &v=f[i][j][k][l];
                        v=0;
                        if(len1>1)v|=(f[i+1][j-1][k][l]&&(a[i]==a[j]));
                        if(len1&&len2)v|=(f[i+1][j][k][l-1]&&(a[i]==b[l]));
                        if(len1&&len2)v|=(f[i][j-1][k+1][l]&&(a[j]==b[k]));
                        if(len2>1)v|=(f[i][j][k+1][l-1]&&(b[k]==b[l]));
                    }
                    if(f[i][j][k][l])res=max(len1+len2,res);
                }
            }
        }
    }
    cout<<res<<endl;
    
}
int main()
{
    int T;
    cin>>T;
    while(T--)
    {
        solve();
    }
}

二、从原串中找子序列

1.不同的子序列—DP

题目链接

y总题解：
在这里插入图片描述

class Solution {
public:
    int numDistinct(string s, string t) {
        int n=s.size(),m=t.size();
        s=" "+s;
        t=" "+t;
        vector<vector<unsigned long long>>f(n+1,vector<unsigned long long>(m+1));
        for(int i=0;i<=n;i++)f[i][0]=1;
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
            {
                f[i][j]=f[i-1][j];
                if(s[i]==t[j])f[i][j]+=f[i-1][j-1];
            }
        return f[n][m];
    }
};

2.Nun Heh Heh Aaaaaaaaaaa—动态规划+快速幂+后缀和

题目链接

详细内容请看代码注解

先不考虑a，先算芳香字符串非a个数，最后个数乘以2的a个数次方-1，相加取模。

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e5+5;
typedef long long LL;
int dp[10][N];
int a[N];//a的后缀数量
const int mod = 998244353;


//预处理后缀中a的个数
void init(string s)
{
    memset(a,0,sizeof a);
    for(int i=s.size();i>=1;i--)
    {
        a[i]=a[i+1]+(s[i]=='a');
    }
}
// 这里别不小心用了龟速乘，我刚才不小心用了龟速乘一直TLE
//后面有几个a，每个a可以选也可以不选所以是2的a次方，但a个数不能为0所以-1
LL qmi(int b)
{
    LL res=1%mod;
    LL a=2;
    while(b){
        if(b&1)res=res*a%mod;
        a=a*a%mod;
        b>>=1;

    }
    return (res-1)%mod;
}
int main()
{
    std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
    int T;
    cin>>T;
    while(T--)
    {
        string s;
        cin>>s;
        //使下标从1开始
        s=" "+s;
        init(s);
        
        //string ss=" nunhehheh";
        
        //dp过程 nunhehheh
        //dp[j][i]表示s前i个字符中ss[1~j]字符串出现次数
        LL res=0;
        for(int i=1;i<=s.size();i++)
        {
            dp[1][i]=(dp[1][i-1]+(s[i]=='n'))%mod;
            dp[2][i]=(dp[2][i-1]+dp[1][i-1]*(s[i]=='u'))%mod;
            dp[3][i]=(dp[3][i-1]+dp[2][i-1]*(s[i]=='n'))%mod;
            dp[4][i]=(dp[4][i-1]+dp[3][i-1]*(s[i]=='h'))%mod;
            dp[5][i]=(dp[5][i-1]+dp[4][i-1]*(s[i]=='e'))%mod;
            dp[6][i]=(dp[6][i-1]+dp[5][i-1]*(s[i]=='h'))%mod;
            dp[7][i]=(dp[7][i-1]+dp[6][i-1]*(s[i]=='h'))%mod;
            dp[8][i]=(dp[8][i-1]+dp[7][i-1]*(s[i]=='e'))%mod;
            dp[9][i]=(dp[8][i-1]*(s[i]=='h'))%mod;
            if(dp[9][i])res=res%mod+(dp[9][i]*qmi(a[i+1]))%mod;
            res%=mod;
        }
        cout<<res<<endl;
    }
}

三、字符串划分问题

1.[NOIP2001]统计单词个数—双重DP+字符串处理

题目链接

双重DP
第一个sum[i][j]预处理i到j中所含有的字符串数量
从后往前判断，便于判断第i个字符是否用上写一个check函数
如果第i个字符用上了x.find（a[i]）==0返回true

第二个dp算最大值
f[i][j]表示前i个字符分为j段的最大值
f [ i ] [ j ] = m a x ( f [ i ] [ j ] , f [ k ] [ j ? 1 ] + s u m [ k + 1 ] [ i ] ) ( j ? 1 < k < i ) f[i][j]=max(f[i][j],f[k][j-1]+sum[k+1][i]) (j-1<k<i) f[i][j]=max(f[i][j],f[k][j?1]+sum[k+1][i])(j?1<k<i)

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 210;
int sum[N][N];
int f[N][45];
string a[10];
int n,m,K;
string s;
bool check(int l,int r)
{
    string ss=s.substr(l,r-l+1);
    for(int i=1;i<=n;i++)
        if(ss.find(a[i])==0)return true;
    return false;
}
int main()
{
    cin>>n>>K;
    s=" ";
    while(n--)
    {
        string _;
        cin>>_;
        s+=_;
    }
    m=s.size()-1;
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int r=m;r>=1;r--)
    {
         for(int l=r;l>=1;l--)
         {
             sum[l][r]=sum[l+1][r];
             if(check(l,r))sum[l][r]++;
         }
        f[r][1]=sum[1][r];
    }
    for(int i=2;i<=m;i++)
        for(int j=2;j<=K;j++)
            for(int k=j-1;k<i;k++)
                f[i][j]=max(f[i][j],f[k][j-1]+sum[k+1][i]);
    cout<<f[m][K]<<endl;
}

2.[SCOI2009]粉刷匠

题目链接

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 52;
int f[N][N][N*N][2];
char g[N][N];
//dp[i][j][k][0/1]
//前i条j段涂k次，最后一段涂红/蓝的最多正确格子数
//红（0）蓝（1）
int main()
{
    int n,m,K;
    cin>>n>>m>>K;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            cin>>g[i][j];
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            for(int k=1;k<=K;k++)
            {
                if(j==1)
                {
                    f[i][j][k][0]=max(f[i-1][m][k-1][0],f[i-1][m][k-1][1])+(g[i][j]=='0');
                    f[i][j][k][1]=max(f[i-1][m][k-1][0],f[i-1][m][k-1][1])+(g[i][j]=='1');
                }
                else
                {
                    f[i][j][k][0]=max(f[i][j-1][k][0],f[i][j-1][k-1][1])+(g[i][j]=='0');
                    f[i][j][k][1]=max(f[i][j-1][k][1],f[i][j-1][k-1][0])+(g[i][j]=='1');
                }
            }
    cout<<max(f[n][m][K][0],f[n][m][K][1])<<endl;
}

四、字符串涂色问题

1.[CQOI2007]涂色PAINT—区间DP

题目链接

f[i][j]为左边界为i，右边界为j的最小涂色次数
如果 s[i]==s[j]
f [ i ] [ j ] = m i n ( f [ i + 1 ] [ j ] , f [ i ] [ j ? 1 ] ) f[i][j]=min(f[i+1][j],f[i][j-1]) f[i][j]=min(f[i+1][j],f[i][j?1])
否则
f [ i ] [ j ] = m i n ( f [ i ] [ j ] , f [ i ] [ k ] + f [ k + 1 ] [ j ] ) ( i = < k < j ) f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]) (i=<k<j) f[i][j]=min(f[i][j],f[i][k]+f[k+1][j])(i=<k<j)

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 55;
int n;
char s[N];
int f[N][N];
int main()
{
    cin>> s+1;
    n=strlen(s+1);
    for(int len=1;len<=n;len++)
    {
        for(int i=1;i+len-1<=n;i++)
        {
            int j=i+len-1;
            if(len==1)f[i][j]=1;
            else if(s[i]==s[j])f[i][j]=min(f[i+1][j],f[i][j-1]);
            else
            {
                for(int k=i;k<j;k++)f[i][j]=min(f[i][k]+f[k+1][j],f[i][j]);
            }
        }
    }
    cout<<f[1][n]<<endl;
}

2.小小粉刷匠

题目链接

这个同理，只是限制区间长度了，加个判断就行了

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=1010;
int f[N][N];
int s[N];
int main()
{
    int n,K;
    cin>>n>>K;
    for(int i=1;i<=n;i++)cin>>s[i];
    memset(f,0x3f,sizeof f);
    for(int len=1;len<=n;len++)
        for(int i=1;i+len-1<=n;i++)
        {
            int j=i+len-1;
            if(i==j)f[i][j]=1;
            else if(len<=K&&s[i]==s[j])f[i][j]=min(f[i+1][j],f[i][j-1]);
            for(int k=i;k<j;k++)f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]);
        }
    cout<<f[1][n]<<endl;
}

3.Color Stripe —DP/贪心

题目链接

贪心写法

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 500010;
signed main()
{
	int n,k;
	cin>>n>>k;
	string s;cin>>s;
	int res=0;
	if(k>2)
	{
		int res=0;
		for(int i=1;i<s.size();i++)
		{
			if(s[i]==s[i-1])
			{
				res++;
				for(int j=0;j<k;j++){
					if('A'+j!=s[i] && 'A'+j!=s[i+1]){
						s[i]='A'+j;
						break;
					}
				}
			}
		}
		cout<<res<<endl;
		cout<<s<<endl;
	}
	else 
	{
		string ss1="A",ss2="B";
		
		int res1=0,res2=0;
		res1+=ss1[0]!=s[0],res2+=ss2[0]!=s[0]; 
		for(int i=1;i<s.size();i++)
		{
			ss1+=ss1[i-1]=='A'?'B':'A';
			ss2+=ss2[i-1]=='A'?'B':'A';
			if(ss1[i]!=s[i])res1++;
			if(ss2[i]!=s[i])res2++;
		}
		if(res1<res2)
		{
			cout<<res1<<endl;
			cout<<ss1<<endl;
		}
		else 
		{
			cout<<res2<<endl;
			cout<<ss2<<endl;
		}
	}
}

DP写法

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 500010;
int f[N][28];
int pre[N][28];
signed main()
{
	int n,m;
	cin>>n>>m;
	string s;
	cin>>s;
	s=" "+s;
	memset(f,0x3f,sizeof f);
	for(int i=0;i<m;i++)f[0][i]=0;
	int minv=1e7;
	for(int i=1;i<=n;i++)
	{
		for(int j=0;j<m;j++)
		{
			for(int k=0;k<m;k++)
			{
				if(k==j)continue;
				if(j+'A'==s[i])
				{
					if(f[i][j]>f[i-1][k])
					{
						pre[i][j]=k;
						f[i][j]=f[i-1][k];
					}	
				}
				else 
				{
					if(f[i][j]>f[i-1][k]+1)
					{
						pre[i][j]=k;
						f[i][j]=f[i-1][k]+1;	
					}
				}
				
			}
		}
	}
	int res=1e7;
	int t;
	for(int i=0;i<m;i++)
	{
		if(f[n][i]<res)
		{
			res=f[n][i];
			t=i;
		}
	}
	cout<<res<<endl;
	string ss="";
	for(int i=n;i>=1;i--)
	{
		ss+=t+'A';
		t=pre[i][t];
	}
	reverse(ss.begin(),ss.end());
	cout<<ss<<endl;
}
  数据结构与算法 最新文章
【力扣106】 从中序与后续遍历序列构造二叉
leetcode 322 零钱兑换
哈希的应用：海量数据处理
动态规划|最短Hamilton路径
华为机试_HJ41 称砝码【中等】【menset】【
【C与数据结构】——寒假提高每日练习Day1
基础算法——堆排序
2023王道数据结构线性表--单链表课后习题部
LeetCode 之 反转链表的一部分
【题解】lintcode必刷50题＜有效的括号序列
上一篇文章      下一篇文章      查看所有文章
加:2022-02-05 21:57:54  更:2022-02-05 21:58:18 
 
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁

360图书馆 购物 三丰科技 阅读网 日历 万年历 2024年11日历 -2024/11/26 17:43:09-

图片自动播放器
↓图片自动播放器↓ 		TxT小说阅读器
↓语音阅读,小说下载,古典文学↓ 		一键清除垃圾
↓轻轻一点,清除系统垃圾↓ 		图片批量下载器
↓批量下载图片,美女图库↓
  网站联系: qq:121756557 email:121756557@qq.com  IT数码