蓝桥杯 3. 涂色

题目描述

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

每次你可以把一段连续的木板涂成一个给定的颜色，后涂的颜色会覆盖先涂的颜色。

例如：

• 第一次把木板涂成 RRRRR
• 第二次涂成 RGGGR
• 第三次涂成 RGBGR，达到目标

请你计算用尽量少的涂色次数达到目标。

---

输入描述

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

• 1 ≤ n ≤ 50

---

输出描述

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

---

输入输出样例

示例 1

输入

AAAAA

输出

1

---

c++代码

#include<bits/stdc++.h>using namespace std;string str;
int n;
vector<vector<int>> dp;int main() {cin >> str;n = str.size();dp = vector<vector<int>>(n, vector<int>(n, INT_MAX));for (int len = 1; len <= n; len++) {for (int i = 0; i + len - 1 < n; i++) {int j = i + len - 1;if (i == j) dp[i][j] = 1;else if (str[i] == str[j]) {int a = INT_MAX, b = INT_MAX;if (i + 1 < n) a = dp[i + 1][j];if (j - 1 >= 0) b = dp[i][j - 1];dp[i][j] = min(a, b);if (dp[i][j] == INT_MAX) dp[i][j] = 1;}else {for (int k = i; k < j; k++) {dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j]);}}}}cout << dp[0][n - 1];return 0;
}//by wqs