F. Clear the String（区间 DP ）//每次都删除一个相同字符的子串，最小多少次

小程序：扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序

https://codeforces.com/contest/1132/problem/F

借鉴：https://www.cnblogs.com/chhokmah/p/10508762.html

题意

给你一个串s，每次可以花费1的代价删去一个子串，要求子串的每一位为同一个字符。
求删去整个串的最小代价。

分析

这是一道非常简单的区间DP问题，我们定义dp[i][j]表示删去子串[i,j][i,j]的最小花费。
就像合并石子一样，我们枚举中间的k，k的范围是i~j。
为了方便解决问题，将k的定义域定义成一个半闭半合区间[i,j)
决策考虑以下：

如果s[k]=s[j]，那么说明当前的区间可以进行消除。
反之，则不能消除。
那么状态转移方程就是：f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]+1−(s[k]==s[j]))

枚举的顺序需要注意，

#include<bits/stdc++.h>

using namespace std;

const int N = ;

char str[N];

long long  dp[N][N];

int main()

{

    int n;scanf("%d%s",&n,str);

    for(int i= ; i<n ; i++)

    dp[i][i]=;

    for(int j= ; j<n ; j++)

    {

        for(int i= ; i<j ; i++ )

        {

            dp[i][j]=0x3f3f3f3f;

            for(int k=i ; k<j ; k++)

            {

                dp[i][j]=min(dp[i][j] , dp[i][k]+dp[k+][j-]+-(int)(str[k]==str[j]));

            }

        }

    }

//    for(int i=0 ; i<n ; i++)

//    {

//        for(int j=i+1 ; j<n ; j++)

//        {

//            dp[i][j]=0x3f3f3f3f;

//            for(int k=i ; k<j ; k++)

//            {

//                dp[i][j] = min(dp[i][j] , dp[i][k] + dp[k+1][j-1] +1 -(str[k]==str[j]));

//            }

//        }

//    }

    printf("%lld\n",dp[][n-]);

}