传送门
题目大意：
让你求最少多少次把格子涂成它想要的。
标题分析：
首先从题面上就能感到浓浓的区间DP的气息，那还想什么呢？开始找题目的突破点吧。
它没有给你涂的固定格式，所以我们可以知道肯定要枚举区间长度。
既然要枚举区间长度，那么我们就可以设dp[i][j]表示第i块到第j块木板的最少涂色次数。
那么我们立马就可以知道dp[i][j]=1(i==j)。
那么如果i!=j呢。
我们需要分情况讨论
当a[i]!=a[j]时，我们就需要把它分开，因为他不管怎么分，小区间已经保证最优了，我们只需要枚举一下然后比较就好啦。
所以它会由dp[i][k]+dp[k+1][j]得来。
当a[i]==a[j]时，因为两端都已经相等了，它要么是最左边的往右涂底色时涂成的，要么就是最右边往左涂底色时涂成的。
所以它会有dp[i][j-1]或dp[i+1][j]得来。
状态转移方程
dp[i][j]=1(i==j) dp[i][j]=min(dp[i][j-1],dp[i+1][j]) (i!=j&&a[i]==b[j]) dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]) (i!=j&&a[i]!=a[j]) 注：k为从i到j的一个端点。
代码
#include<bits/stdc++.h>
using namespace std
;
int dp
[70][70];
int len
;
char a
[70];
int f
[70];
int main()
{
cin
>>a
+1;
len
=strlen(a
+1);
for(int i
=1;i
<=len
;i
++) f
[i
]=a
[i
]-'A'+1;
memset(dp
,0x3f,sizeof(dp
));
for(int i
=1;i
<=len
;i
++) dp
[i
][i
]=1;
for(int n
=1;n
<=len
-1;n
++)
{
for(int i
=1,j
=i
+n
;j
<=len
;j
++,i
++)
{
if(f
[i
]==f
[j
])
dp
[i
][j
]=min(dp
[i
][j
-1],dp
[i
+1][j
]);
else
for(int k
=i
;k
<=j
;k
++)
dp
[i
][j
]=min(dp
[i
][j
],dp
[i
][k
]+dp
[k
+1][j
]);
}
}
cout
<<dp
[1][len
];
return 0;
}
