题目链接

题目描述

假设你有一条长度为 $5$ 的木版，初始时没有涂过任何颜色。你希望把它的 $5$ 个单位长度分别涂上红、绿、蓝、绿、红色，用一个长度为 $5$ 的字符串表示这个目标：RGBGR。

每次你可以把一段连续的木版涂成一个给定的颜色，后涂的颜色覆盖先涂的颜色。例如第一次把木版涂成 RRRRR，第二次涂成 RGGGR，第三次涂成 RGBGR，达到目标。

用尽量少的涂色次数达到目标。

输入格式

输入仅一行，包含一个长度为 $n$ 的字符串，即涂色目标。字符串中的每个字符都是一个大写字母，不同的字母代表不同颜色，相同的字母代表相同颜色。($1≤n≤50$)

输出格式

仅一行，包含一个数，即最少的涂色次数。

题解

初始为空，要达到最终状态，我们总是需要选择一段涂上颜色。可以很快想到用区间 $\text{DP}$。

考虑这么一个问题，若给定状态中只用涂上一个字符，我们一定只用涂一次。这也就是边界条件 $f_{i,i}=1$。

而对于颜色相同而非同一个字符的情况，多涂一个总是无伤大雅的，也就是 $f{i,j}=\min(f{i+1,j},f_{i,j-1})$。

总后也就是我们常用的区间 $\text{DP}$，枚举一个分割点进行 $\text{DP}$。

#include <bits/stdc++.h>
using namespace std;
char a[105];
int f[105][105];
/*
f[l][r]  = 	min{ f[l + 1][r], f[l][r - 1] }(a[l] = a[r]),
		min{ f[l][k] + f[k + 1][r], f[l][r] }
*/

int main() {
    scanf("%s", a + 1);
    int length = strlen(a + 1);
    memset(f, 0x3f, sizeof(f));
    for (int i = 1; i <= length; i++) f[i][i] = 1;
    for (int len = 1; len < length; len++)
        for (int l = 1; l + len <= length; l++) {
            int r = l + len;
            if (a[l] == a[r])
                f[l][r] = min(f[l + 1][r], f[l][r - 1]);
            else
                for (int k = l; k < r; k++) f[l][r] = min(f[l][k] + f[k + 1][r], f[l][r]);
        }
    printf("%d", f[1][length]);
    return 0;
}