# [CQOI2007]涂色
## 题目描述
假设你有一条长度为 $5$ 的木板，初始时没有涂过任何颜色。你希望把它的 $5$ 个单位长度分别涂上红、绿、蓝、绿、红色，用一个长度为 $5$ 的字符串表示这个目标：$\texttt{RGBGR}$。
每次你可以把一段连续的木板涂成一个给定的颜色，后涂的颜色覆盖先涂的颜色。例如第一次把木板涂成 $\texttt{RRRRR}$，第二次涂成 $\texttt{RGGGR}$，第三次涂成 $\texttt{RGBGR}$，达到目标。
用尽量少的涂色次数达到目标。
## 输入格式
输入仅一行，包含一个长度为 $n$ 的字符串，即涂色目标。字符串中的每个字符都是一个大写字母，不同的字母代表不同颜色，相同的字母代表相同颜色。
## 输出格式
仅一行，包含一个数，即最少的涂色次数。
## 样例 #1
### 样例输入 #1
```
AAAAA
```
### 样例输出 #1
```
1
```
## 样例 #2
### 样例输入 #2
```
RGBGR
```
### 样例输出 #2
```
3
```
## 提示
$40\%$ 的数据满足 $1\le n\le 10$。
$100\%$ 的数据满足 $1\le n\le 50$。
by reactord @ 2022-07-25 23:42:00
f
i,j
=1 (i==j)
f_{i,j}=\min(f_{i,j-1},f_{i+1,j})\ (i!=j,\ s_i==s_j)
f
i,j
=min(f
i,j−1
,f
i+1,j
) (i!=j, s
i
==s
j
)
f_{i,j}=\min(f_{i,j},f_{i,k}+f_{k+1,j})\ (i!=j,\ s_i!=s_j,\ i\le k<j)
f
i,j
=min(f
i,j
,f
i,k
+f
k+1,j
) (i!=j, s
i
!=s
j
, i≤k<j)
by reactord @ 2022-07-25 23:43:40
CE
by reactord @ 2022-07-25 23:44:20
@[caramel_qwq](/user/444195)
在DP前就要把每个`dp[i][i]`赋值为$1$，如果一边DP一边赋值，可能出现从`dp[i][i]`转移时`dp[i][i]`未赋值的情况。
by DTCT @ 2022-07-26 00:21:04
@[LMY08](/user/442644)
```cpp
#include<bits/stdc++.h>
using namespace std;
int dp[58][58];
string s;
int main(){
cin>>s;
s=' '+s+' ';
int n=s.size()-1;
for(int i=1;i<=50;i++) dp[i][i]=1;
for(int len=2;len<=n;len++){
for(int i=1;i+len-1<=n;i++){
int j=i+len-1;
if(i!=j&&s[i]==s[j]) dp[i][j]=min(dp[i+1][j],dp[i][j-1]);
if(i==j&&s[i]!=s[j]){
for(int k=i;k<j;k++){
dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]);
}
}
}
}
cout<<dp[1][n]<<"\n";
return 0;
}
```
所以您是指这样吗
by caramel_qwq @ 2022-07-26 14:57:36
@[caramel_qwq](/user/444195)
1. $n$应是`s.size()-2`
2. 整个dp数组要赋初值
3. if中不需要`i!=j`和`i==j`
by DTCT @ 2022-07-26 16:31:23
@[LMY08](/user/442644) 3ks
by caramel_qwq @ 2022-07-26 16:45:40
@[caramel_qwq](/user/444195) 不谢，都是沃家人
by DTCT @ 2022-07-26 22:07:55