题目链接

题目要求

给定一个长度为n仅有小写字母的字符串s.你可以对这个字符串进行以下操作：如果一个连续的子串里的字符都相等那么你就可以直接删除这一整个字串，要求计算删除s的最小需要步数

数据范围

1≤n≤500

这道题其实一眼可以看出来应该要用区间DP，并且这道题跟洛谷上的一道题很相似：涂色。

我们直接套用区间DP来思考这道题：一般情况下删除一整段区间的最小步数我们可以按照普通的区间DP一样遍历分界线去找，但是这里要注意的一点是有可能我删去一段子区间后使得两端相同的字母合并，此时我只需再用一次删除操作便可。我们可以发现重点在于两端。这种情况只会发生在两端。所以每次我们遍历大区间的时候，首先先判断两端是否相等，如果相等代表什么？是不是代表着某一端的字母相当于没有进行操作，所以此时的操作次数其实就是去掉某一端之后的区间所需操作次数。

如果做过上面洛谷的那道涂色题就会很好转变思路过来，那就称其为涂色类区间DP吧。
代码如下：

#include<bits/stdc++.h>

using namespace std;

#define int long long
const int MOD=1e9+7;
const int N=1000100;

void init() {
   

}

int a[N];
int dp[505][505];

void solve() {
   
    init();

    int n;
    cin>>n;
    string s;
    cin>>s;

    memset(dp,MOD,sizeof dp);

    for(int i=1;i<=n;i++) dp[i][i]=1;

    for(int len=2;len<=n;len++) {
   
        for(int i=1;i+len-1<=n;i++) {
   
            int j=i+len-1;
            if(s[i-1] == s[j-1]) {
   
                dp[i][j] = min(dp[i][j],dp[i+1][j]);
            }
            else {
   
                for(int mid=i;mid<j;mid++) {
   
                    dp[i][j] = min(dp[i][j],dp[i][mid] + dp[mid+1][j]);
                }
            }
        }
    }

    cout<<dp[1][n]<<"\n";
}


signed main() {
   
     //ios::sync_with_stdio(false);
     //cin.tie(0);
     //cout.tie(0);

    int t=1;
    //cin>>t;

    while(t--) {
   
        solve();
    }
    return 0;
}