区间dp-基础题目4

题目链接

1 解题思路

这道题我可以想如果字符串长度为1时，答案是0。如果长度是2，两个字符相同，答案是0；两个字符不同，再在边上插入其中一个字符即可，答案是1。如果长度是3，边上的两个字符相同，答案是0；边上字符不同，可以是在字符串末尾插入第一个字符，答案是原来三个字符中后两个字符组成回文串要插入的最少字符数+1；也可以是在开头插入最后一个字符，答案是原来三个字符中前两个字符组成回文串要插入的最少字符数+1，两种做法取最小值。如果长度为4，边上的两个字符相同，答案是四个字符中间两个字符组成回文串要插入的最少字符数；边上字符不同，可以是在字符串末尾插入第一个字符，答案是原来三个字符中后三个字符组成回文串要插入的最少字符数+1；也可以是在开头插入最后一个字符，答案是原来四个字符中前三个字符组成回文串要插入的最少字符数+1，两种做法取最小值。依此类推…

2 实现思路

2.1 数组定义及状态转移方程

于是我们可以定义dp数组，dp[i][j]表示第i个字符到第j个字符组成回文串需要插入的最小字符数。状态转移方程：

if(s[i–1]==s[j–1]) dp[i][j]=min(dp[i][j],dp[i+1][j–1]);
dp[i][j]=min(dp[i][j],dp[i+1][j]+1);
dp[i][j]=min(dp[i][j],dp[i][j–1]+1);

2.2 逆向枚举左端点

通过分析，我发现按照上图的方向去更新dp数组可以得到答案。实际上长度为1和长度为2时可以单独拎出来讨论，所以实现代码如下：

for(int i=1;i<=n;i++) dp[i][i]=0;
for(int i=2;i<=n;i++){
if(s[i–1]==s[i–2]) dp[i–1][i]=0;
else dp[i–1][i]=1;
}
for(int i=n;i>=1;i—){
for(int j=i+2;j<=n;j++){
if(s[i–1]==s[j–1]) dp[i][j]=min(dp[i][j],dp[i+1][j–1]);
dp[i][j]=min(dp[i][j],dp[i+1][j]+1);
dp[i][j]=min(dp[i][j],dp[i][j–1]+1);
}
}

3 AC Code

#include<bits/stdc++.h>
using namespace std;
#define int long long
string s;
int n,dp[1005][1005];
signed main(){
cin>>s;
n=s.size();
memset(dp,0x3f,sizeof(dp));
for(int i=1;i<=n;i++) dp[i][i]=0;
for(int i=2;i<=n;i++){
if(s[i–1]==s[i–2]) dp[i–1][i]=0;
else dp[i–1][i]=1;
}
for(int i=n;i>=1;i—){
for(int j=i+2;j<=n;j++){
if(s[i–1]==s[j–1]) dp[i][j]=min(dp[i][j],dp[i+1][j–1]);
dp[i][j]=min(dp[i][j],dp[i+1][j]+1);
dp[i][j]=min(dp[i][j],dp[i][j–1]+1);
}
}
cout<<dp[1][n];
return 0;
}

还有一种是LCS实现，把输入的s到倒序存储到t，用f[n]存储s和t的最长公共子序列。我们要让正反读起来是一样的，目前只有f[n]个字符能匹配，剩下不能匹配的我们要在中心的另一边加上去，所以答案是n-f[n]。

#include<bits/stdc++.h>
using namespace std;
#define int long long
int f[1005];
string s,t;
signed main(){
cin>>s;
t=s;
reverse(t.begin(),t.end());
int n=s.size();
for(int i=1;i<=n;i++){
int pre=0;
for(int j=1;j<=n;j++){
int tmp=f[j];
if(s[i–1]==t[j–1]) f[j]=pre+1;
else f[j]=max(f[j],f[j–1]);
pre=tmp;
}
}
cout<<n–f[n];
return 0;
}