$这题刚拿到手上一脸懵逼，根本不懂怎么定义状态，题解也似乎是一眼得区间dp。$这题似乎还不同于石子合并这种区间dp的模板题，更加抽象一点。

个人认为区间$dp$一般解决的都是一段连续区间上的问题，且转移总是和区间边界上的值有关系，且小区间很容易合并成大区间。这里非常贴近，因为有回文串这个条件，回文串就是比较的边界上两个端点是否相同。

$思路：如果一个串左右端i和j相同，很明显只关心s[i+1,j-1]里面少了几个就够了。但是不同的话$，说明肯定左右有一个是缺少对称的，至于哪一个缺少另一边对称，答案组合会更小，需要取另外两个区间少了几个的最小值：$min([i,j-1],[i+1，j])。$

1.状态定义:$dp(i,j) 表示区间[i,j]里去掉字符变成子串str(i,j)的集合，属性是min。$

2.状态转移:

$dp(i,i)=0 \;单个字符就是回文串$
$dp(i,j)=dp(i+1,j-1)(s[i]==s[j]) $
$dp(i,j)=min(dp(i+1,j),dp(i,j-1))+1 (s[i]\not=s[j])$

3.$递推顺序：因为要用到后面i+1的状态，所以i要倒过来枚举。$

4.初始化：所有状态最好初始化成很大的数，因为我要取最小值。

5.注意事项：

$（1）当i==j-1且s[i]==s[j]时，这也是回文串，但是dp(i+1,j-1)是不合法的，被声明称了INF$，所以要单独拿出来讨论。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#include<string>
#include<map>
#include<set>
#include<unordered_map>
#include<unordered_set>
#include<queue>
#include<stack>
#include<climits>
#define x first
#define y second
#define MP make_pair
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;

const int N = 1e3 + 5;
char str[N];
int dp[N][N];

int main(void){

    scanf("%s", str);

    int n = strlen(str);
    for (int i = 0 ; i < N; ++i)
        for (int j = 0; j < N; ++j)
            dp[i][j] = 2e9;
    //f(i, j) = max(f(i + 1, j - 1) + 2, f(i + 1, j), f(i, j - 1), f(i + 1, j - 1))



    for (int i = n - 1; i > -1; --i){
        for (int j = i; j < n; ++j){
            if (i == j) dp[i][j] = 0;
            else {
                if (str[i] == str[j]){
                    if (i == j - 1) dp[i][j] = 0;
                    else dp[i][j] = min(dp[i][j], dp[i + 1][j - 1]);
                }
                else dp[i][j] = min(dp[i + 1][j] + 1, min(dp[i][j - 1] + 1, dp[i][j]));
            }
        }
    }

    cout << dp[0][n - 1];
    return 0;
}