思路
考虑区间 DP。
设 \(f_{i, j}\) 表示要刷到 \([i, j]\) 这一段的目标需要的最小次数。
对于 \(f_{i, j}\)，
如果 \(color_i\) 与 \(color_j\) 相等，那么再子区间合并的时候就可以少刷一次，即 \(f_{i, j} = \min\limits_{k = i}^{j - 1}f_{i, k} + f_{k + 1, j} - 1\)。
否则 \(f_{i, j} = \min\limits_{k = i}^{j - 1}f_{i, k} + f_{k + 1, j}\)。
代码
#include <bits/stdc++.h>
using namespace std;
const int N = 310, INF = 0x3f3f3f3f;
int f[N][N];
int n, a[N];
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
for (int len = 1; len <= n; len++) {
for (int i = 1; i + len - 1 <= n; i++) {
int j = i + len - 1;
if (len == 1) f[i][j] = 1;
else {
f[i][j] = INF;
for (int k = i; k < j; k++) {
if (a[i] == a[j]) f[i][j] = min(f[i][j], f[i][k] + f[k + 1][j] - 1);
else f[i][j] = min(f[i][j], f[i][k] + f[k + 1][j]);
}
}
}
}
cout << f[1][n] << '\n';
return 0;
}