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-]);
}