[CQOI2007]涂色PAINT

题目地址：

https://ac.nowcoder.com/acm/problem/19909

基本思路：

数据范围：,
考虑区间,设表示将区间染色需要的最少染色次数,
然后我们考虑如何将区间合并,由于我们对于一段连续的区间可以在一次内涂完,
这就意味着如果我们就可以直接从和位置的答案里转移过来。
否者，我们就要枚举断点,将区间分为两部分染色，并将两部分的结果相加，取最小的。
具体转移方程如下:

,

,

,

参考代码：

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;
#define IO std::ios::sync_with_stdio(false); cin.tie(0)
#define int long long
#define rep(i, l, r) for (int i = l; i <= r; i++)
#define per(i, l, r) for (int i = l; i >= r; i--)
#define mset(s, _) memset(s, _, sizeof(s))
#define pb push_back
#define pii pair <int, int>
#define mp(a, b) make_pair(a, b)
#define INF (int)1e18

inline int read() {
  int x = 0, neg = 1; char op = getchar();
  while (!isdigit(op)) { if (op == '-') neg = -1; op = getchar(); }
  while (isdigit(op)) { x = 10 * x + op - '0'; op = getchar(); }
  return neg * x;
}
inline void print(int x) {
  if (x < 0) { putchar('-'); x = -x; }
  if (x >= 10) print(x / 10);
  putchar(x % 10 + '0');
}

const int maxn = 55;
int dp[maxn][maxn];
string s;
signed main() {
  IO;
  cin >> s;
  int n = s.size();
  s = ' ' + s;
  mset(dp,0x3f);
  for(int len = 1; len <= n ; len++){
    for(int l = 1 ; l + len - 1 <= n ; l++) {
      int r = l + len - 1;
      if(len == 1){
        dp[l][r] = 1;
        continue;
      }
      if (s[l] == s[r]) dp[l][r] = min(dp[l + 1][r], dp[l][r - 1]);
      else {
        for (int k = l; k < r; k++) dp[l][r] = min(dp[l][r], dp[l][k] + dp[k + 1][r]);
      }
    }
  }
  cout << dp[1][n] << '\n';
  return 0;
}