省流：区间 DP
题目传送门
这种蓝的区间 DP 还是有亿点点费脑子的，实在不行点开题解深度膜拜一下
正片开始
首先使用区间 DP 的基础操作，设 \(dp[i][j]\) 表示给区间 \([l,r]\) 染色的最小步数，于是答案为
\[dp[0][n - 1]
\]
为啥是 \(0\) 到 \(n-1\) 呢？因为我们的字符串是从 \(0\) 开始存的，这里的 \(n\) 表示字符串长度。
你是在看不习惯的话可以存字符数组然后
scanf("%s", s + 1)
或者在字符串前面加上一空格，这里不多赘述。
考虑 DP 的边界。
考虑啥？给 \([i,i]\) 染色不就一步的事吗？于是
for (int i = 0; i < (int)s.size(); i++)dp[i][i] = 1;
考虑 DP 的转移方程。
考虑啥？分类讨论呗。
\(1^\circ\) 若 \(s_l=s_r\)，可以在 \([l,r-1]\) 的基础上不改变步数地涂色，于是
\[dp[l][r]=dp[l][r-1]
\]
\(2^\circ\) 若 \(s_l \ne s_r\)，则 \(\exists x \in [l,r)\)，使得不存在左端点 \(l'<=x\) 且右端点 \(r'>x\) 的染色。枚举 \(x\) 即可。
于是乎
\[dp[l][r]=\min_{i=l}^{r} dp[l][i]+dp[i+1][r]
\]
这个转移方程也是非常符合区间 DP 的风格。
code
/*********************************************************** Author : dingziyang888* Website : https://www.luogu.com.cn/problem/* Created Time :* FileName :* Warning!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!* 1.MLE?* 2.array size enough?* 3.long long?* 4.overflow long long?* 5.multiple task cleaned?* 6.freopen?* 7.TLE?* *******************************************************/
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <iterator>
#include <map>
#include <unordered_map>
#include <queue>
#include <string>
#include <cstring>
#include <set>
#include <bitset>
#include <unordered_set>
#include <vector>
#include <deque>
#include <iomanip>
#include <fstream>
#include <sstream>
#include <list>
#include <array>
#include <iterator>
#include <cmath>
#include <new>
#include <random>
#include <cfloat>
#include <cstdlib>
#include <climits>
#include <numeric>
#include <complex>
#include <ctime>
#include <chrono>
#include <thread>
#include <mutex>
#include <future>
#include <exception>
#include <stdexcept>
#include <cstdint>
#include <cassert>
#include <stack>
#include <cctype>
#define DEBUG
#define Ofile(s) freopen(s".in", "r", stdin), freopen (s".out", "w", stdout)
#define Cfile(s) fclose(stdin), fclose(stdout)
#define fast ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
using namespace std;using ll = long long;
using ull = unsigned long long;
using lb = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using pil = pair<int, ll>;
using pli = pair<ll, int>;constexpr int mod = 998244353;
constexpr int maxk = 55;int dp[maxk][maxk];string s;int main() {fast;cin >> s;for (int i = 0; i < (int)s.size(); i++)dp[i][i] = 1;for (int l = 1; l < (int)s.size(); l++)for (int i = 0; i + l < (int)s.size(); i++)if (s[i] == s[i + l])dp[i][i + l] = dp[i][i + l - 1];else {dp[i][i + l] = dp[i][i] + dp[i + 1][i + l];for (int j = i + 1; j < i + l; j++)dp[i][i + l] = min(dp[i][i + l], dp[i][j] + dp[j + 1][i + l]);}cout << dp[0][(int)s.size() - 1];return 0;
}