下面这是代码

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 55;

string str;

int dp[MAXN][MAXN];

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  getline(cin, str);
  int n = str.size();
  for (int len = 1; len <= n; ++len) {
    for (int l = 0; l + len - 1 < n; ++l) {
      int r = l + len - 1;
      if (len == 1)
        dp[l][r] = 1;
      else {
        if (str[l] == str[r]) {
          dp[l][r] = dp[l + 1][r];
        } else {
          dp[l][r] = numeric_limits<int>::max();
          for (int k = l; k < r; ++k) {
            dp[l][r] = min(dp[l][k] + dp[k + 1][r], dp[l][r]);
          }
        }
      }
    }
  }
  cout << dp[0][n - 1] - 1 << endl;
}

真离谱，减一之前能过样例，但提交上去全WA

减一之后样例全过不了，但AC了。。。。