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

题意：

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

例如abcddcba中的"dd"

求删去整个串的最小代价。1≤|s|≤500

思路：

子状态为dp[i][j]表示消除区间[i,j]内所有字母所需的最小步数。

考虑两种转移。

1. 与上一个状态相比，假设新的字母不能缩短步数，那么代价直接加1。

dp[i][j]=min(dp[i+1][j],dp[i][j−1])+1。

2. 可以缩短步数。那么枚举与哪一个字母相同。

如果c[i]==c[k]，则dp[i][j]=min(dp[i][j],dp[i+1][k−1]+dp[k][j])。

在维护上有一个需要注意的细节：因为第一种转移需要dp[i+1][j]和dp[i][j−1]的数据，所以我们需要先枚举j再枚举i，同时i从大到小枚举。