一些简单的子序列dp问题
问题一：最长上升子序列
int seq(vector<int>&a){
int n=a.size();
int dp[n+1];
int len=1;
dp[1]=a[0];
for(int i=1;i<n;i++){
if(dp[len]<a[i])dp[++len]=a[i];
else dp[lower_bound(dp+1,dp+1+len,a[i])-dp]=a[i];
}
return len;
}
问题二:最长公共子序列
找出序列中最长公共子序列
设
为
中的最长公共子序列
如果
否则
int longestCommonSubsequence(string s, string t) {
int n=s.size(),m=t.size();
vector<vector<int>>dp(n+1,vector<int>(m+1,0));
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(s[i-1]==t[j-1])dp[i][j]=dp[i-1][j-1]+1;
else dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
}
}
return dp[n][m];
}
问题三:最长公共子串
序列中最长公共子串
int fun(string s,string t){
int n=s.size(),m=t.size();
int ans=0;
vector<vector<int>>dp(n+1,vector<int>(m+1,0));
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(s[i-1]==t[j-1])
dp[i][j]=dp[i-1][j-1]+1;
ans=max(ans,dp[i][j]);
}
}
return ans;
}
问题四：字符串中本质不同子序列的个数
比如
本质不同的有
个。
考虑重复的话
，对于这个解释是
所以去重的话，只要去掉上次
出现的位置中
Jik
int dp[N],last[30];
int fun(string s){
int n=s.size();
for(int i=1;i<=n;i++){
dp[i]=dp[i-1]*2+1;
if(last[s[i-1]])dp[i]-=1+dp[last[s[i-1]]-1];
last[s[i-1]]=i;
dp[i]=(dp[i]%mod+mod)%mod;
}
return dp[n];
}
问题五：本质不同的子序列个数，且子序列长度固定
对于字符串，子序列长度为
且本质不同的个数。
设表示
中长度为
的序列个数。
那么
肯定是
中长度为
的加上
和
中长度
组成长度
的
即
，对于重复的
即可。
int fun(){
for(int i=0;i<=n;i++)dp[i][0]=1;
for(int i=1;i<=n;i++){
for(int j=1;j<=k;j++){
dp[i][j]=dp[i-1][j]+dp[i-1][j-1];
if(last[s[i]])dp[i][j]-=dp[last[s[i]]-1][j-1];
}
last[s[i]]=i;
}
return O(dp[n][k]);
}
问题六:子序列相等的个数
序列中子序列相同的个数
比如
三个相同
设
表示
中的个数，
显然对于
对于
可以得到
这一合法答案，所以
但是
可以和
任意一个合法的序列构造成一个新序列所以还要加上
所以
int fun(string s,string t){
int n=s.size(),m=t.size();
vector<vector<int>>dp(n+1,vector<int>(m+1,0));
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(s[i-1]==t[j-1])
dp[i][j]=dp[i-1][j]+dp[i][j-1]+1;
else
dp[i][j]=dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1];
dp[i][j]%=mod;
}
}
return dp[n][m];
}
问题七：s串中子序列和t串相同的个数
设表示
如果
和
不相等，那么可能
和
有匹配的，所以
如果相等，
int numDistinct(string s, string t) {
int n=s.size(),m=t.size();
vector<vector<int>>dp(n+1,vector<int>(m+1,0));
for(int i=0;i<=n;i++)dp[i][0]=1;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
dp[i][j]=dp[i-1][j];
if(s[i-1]==t[j-1])
dp[i][j]+=dp[i-1][j-1];
}
}
return dp[n][m];
}
问题八:s串中子序列和t串中子串相等的个数。
问题九：编辑距离
s串可以任意删除，添加，替换字符使得和t串相等，求最小花费。
设为将
变成
的最小花费。
如果
显然直接
就行了。
如果不相等那么
可能会被替换
，删除
,添加
所以
int minDistance(string a, string b) {
int m=a.size(),n=b.size();
vector<vector<int>>dp(m+1,vector<int>(n+1,0));
for(int i=1;i<=m;i++)dp[i][0]=i;//a[1,i]变成空串的花费
for(int i=1;i<=n;i++)dp[0][i]=i;//空串变成b[1,i]的花费
for(int i=1;i<=m;i++){
for(int j=1;j<=n;j++){
if(a[i-1]==b[j-1])dp[i][j]=dp[i-1][j-1];
else dp[i][j]=min(dp[i-1][j],min(dp[i][j-1],dp[i-1][j-1]))+1;
}
}
return dp[m][n];
}
问题十：字符串分割成回文串的最少次数。
给定一个字符串 s，将 s 分割成一些子串，使每个子串都是回文串。
返回符合要求的最少分割次数。
设为
中的最少次数，如果
是回文串,那么
。
bool is[2005][2005];
int dp[2005];
int minCut(string s) {
int n=s.size();
for(int i=1;i<=n;i++){
for(int j=i;j>=1;j--){
if(i==j){is[i][j]=true;continue;}
if(s[i-1]==s[j-1]&&(is[j+1][i-1]||j==i-1)){
is[j][i]=true;
}
}
}
for(int i=1;i<=n;i++){
dp[i]=2006;
for(int j=i;j>=1;j--){
if(is[j][i]){
dp[i]=min(dp[i],1+dp[j-1]);
}
}
}
return dp[n]-1;
}
问题十一：取完字符串s的最少次数，每次取回文子串，剩下的拼接在一起.
比如,先取
,再取
总共
次。
设
为区间
取完的最小花费。
int minimumMoves(vector<int>& a) {
//dp[i][j] 表示删除区间[i,j]最小的步数
int dp[111][111],n=a.size();
memset(dp,0x3f3f,sizeof(dp));
for(int i=0;i<n;i++)dp[i][i]=1;//删除一个数是1
for(int i=1;i<n;i++){//判断相邻的步数
if(a[i]==a[i-1])dp[i-1][i]=1;
else dp[i-1][i]=2;
}
for(int len=2;len<n;len++){
for(int i=0;i+len<n;i++){
int j=len+i;//枚举区间[i,i+len]
for(int k=i;k<j;k++)dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]);
if(a[i]==a[j]){
dp[i][j]=min(dp[i][j],dp[i+1][j-1]);
}
}
}
return dp[0][n-1];
}
问题十二：正则表达式匹配 给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 '.' 和 '*' 的正则表达式匹配。
'.' 匹配任意单个字符
'*' 匹配零个或多个前面的那一个元素
bool isMatch(string s, string p) {
s=" "+s;
p=" "+p;
int m=s.size(),n=p.size();
vector<vector<bool>>dp(m+1,vector<bool>(n+1,false));
dp[0][0]=true;
for(int i=1;i<=m;i++){
for(int j=1;j<=n;j++){
if(s[i-1]==p[j-1]||p[j-1]=='.')dp[i][j]=dp[i-1][j-1];
else if(p[j-1]=='*'){
if(s[i-1]!=p[j-2]&&p[j-2]!='.')dp[i][j]=dp[i][j-2];
else dp[i][j]=dp[i-1][j]||dp[i][j-2]||dp[i][j-1];
}
}
}
return dp[m][n];
}
问题十三：给定一个字符串s，和一个整数k，允许替换字符，将s分割成k个回文串，求最小修改次数。
设为
中分割成
段的最少次数，所以可以枚举
.
为
变为回文串的最小花费。
和这题思路一样
int f[104][104];
int dp[105][105];
int palindromePartition(string s, int k) {
int n=s.size();
function<int(int l,int r)>chan=[&](int l,int r){
int ans=0;
while(l<r){
ans+=s[l-1]!=s[r-1];
l++,r--;
}
return ans;
};
for(int i=1;i<=n;i++){
f[i][i]=0;
for(int j=i+1;j<=n;j++){
f[i][j]=chan(i,j);
}
dp[i][1]=f[1][i];
}
for(int i=2;i<=k;i++){
for(int j=i;j<=n;j++){
dp[j][i]=n;
for(int l=1;l<j;l++){
dp[j][i]=min(dp[j][i],dp[l][i-1]+f[l+1][j]);
}
}
}
return dp[n][k];
}
问题十四：给定三个字符串 s1, s2, s3, 验证 s3 是否是由 s1 和 s2 交错组成的。 比如s1="ab",s2="ac",s3="aacb" 这是合法的。
表示
是否匹配到
。
bool isInterleave(string s1, string s2, string s3) {
int m=s1.size(),n=s2.size();
if(m+n!=s3.size())return 0;
vector<vector<int>>dp(m+1,vector<int>(n+1,0));
dp[0][0]=1;
for(int i=0;i<=m;i++){
for(int j=0;j<=n;j++){
if(i)dp[i][j]|=s1[i-1]==s3[i+j-1]&&dp[i-1][j];
if(j)dp[i][j]|=s2[j-1]==s3[i+j-1]&&dp[i][j-1];
}
}
return dp[m][n];
}
问题十五：给定字符串s1,s2,找到一个字符串s3,满足s3的子序列包含s1,s2，并且s3长度最短。 比如s1="ab",s2="ac",s3="abc"符合。 只需要求出最长公共子序列即可。
int dp[1011][1011];
string shortestCommonSupersequence(string s1, string s2) {
int m=s1.size(),n=s2.size();
for(int i=1;i<=m;i++){
for(int j=1;j<=n;j++){
if(s1[i-1]==s2[j-1])dp[i][j]=dp[i-1][j-1]+1;
else dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
}
}
int t=dp[m][n];
int x=m,y=n;
vector<char>v;
while(t){
if(dp[x-1][y]!=t&&dp[x][y-1]!=t){
v.push_back(s1[x-1]);
t--;x--,y--;
continue;
}
if(dp[x-1][y]==t)x--;
else y--;
}
reverse(v.begin(),v.end());
string s="";
int i=0,j=0;
for(int k=0;k<v.size();k++){
while(i<m&&s1[i]!=v[k])s+=s1[i++];i++;
while(j<n&&s2[j]!=v[k])s+=s2[j++];j++;
s+=v[k];
}
while(i<m)s+=s1[i++];while(j<n)s+=s2[j++];
return s;
}
问题十六：给你一个字符串 s ，每一次操作你都可以在字符串的任意位置插入任意字符。 请你返回让 s 成为回文串的 最少操作次数 。 其实结论就是，不用增加的肯定是s的最长回文子序列，只要找出最长回文子序列的长度就是不需要增加的字符。 最长回文子序列可以将s反过来求最长公共子序列。 这个问题和删除任意字符，使得s是回文串等价。
int dp[505][505];
int minInsertions(string s) {
int n=s.size();
for(int i=1;i<=n;i++){// dp[i][j]区间[i,j]的最长回文子序列。
dp[i][i]=1;
for(int j=i-1;j>=1;j--){
if(s[i-1]==s[j-1])dp[j][i]=dp[j+1][i-1]+2;
else dp[j][i]=max(dp[j+1][i],dp[j][i-1]);
}
}
return n-dp[1][n];
}
or
int dp[505][505];
int minInsertions(string s) {
string t(s.rbegin(),s.rend());
int n=s.size();
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(s[i-1]==t[j-1])dp[i][j]=dp[i-1][j-1]+1;
else dp[i][j]=max(dp[i][j-1],dp[i-1][j]);
}
}
return n-dp[n][n];
}
问题十七：删去字符串s中最多k个字符使得字符串是回文串。 其实反过来想，将一个字符串增加至少k个字符变成回文串，就变成上面那个问题，前后的最长回文子序列没有发生变化。所以只需要最长回文子序列加K看是否大于n就行。
int dp[505][505];
bool fun(string s,int k) {
int n=s.size();
for(int i=1;i<=n;i++){// dp[i][j]区间[i,j]的最长回文子序列。
dp[i][i]=1;
for(int j=i-1;j>=1;j--){
if(s[i-1]==s[j-1])dp[j][i]=dp[j+1][i-1]+2;
else dp[j][i]=max(dp[j+1][i],dp[j][i-1]);
}
}
return k+dp[1][n]>=n;
}
查看13道真题和解析