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

題意：

給你一個串 s，每次可以花費 1 的代價刪去一個子串，要求子串的每一位為同一個字符。

例如abcddcba中的"dd"

求刪去整個串的最小代價。1≤|s|≤500

思路：

子狀態(tài)為dp[i][j]表示消除區(qū)間[i,j]內(nèi)所有字母所需的最小步數(shù)。

考慮兩種轉(zhuǎn)移。

1. 與上一個狀態(tài)相比，假設(shè)新的字母不能縮短步數(shù)，那么代價直接加1。

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

2. 可以縮短步數(shù)。那么枚舉與哪一個字母相同。

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

在維護(hù)上有一個需要注意的細(xì)節(jié)：因為第一種轉(zhuǎn)移需要dp[i+1][j]和dp[i][j?1]的數(shù)據(jù)，所以我們需要先枚舉j再枚舉i，同時i從大到小枚舉。