为了做这道题并且理解,做了一个晚上。。。
洛谷这道题的题解简直就是在背模板,啥都看不懂(对我这种juruo来说
算法
(区间$DP$)
令输入的字符串为$str.$
设 $dp[i][j]$ 表示 $[str[i],str[j]]$ 的区间最少染色次数。
当 $dp[i][j]$ 满足 $i=j$ 时,有:
$$dp[i][j]=1$$
表示i到i只需要1次染色次数
当 $dp[i][j]$ 满足 $i\not = j \And str[i]\not = str[j]$ 时,有:
$$dp[i][j]=min(dp[i][k]+dp[k+1][j])$$
$k$ 为 $[i,j)$ 之间的一个断点,就是区间DP的常见套路。$i$ 为左端点, $j$ 为右端点。
当 $dp[i][j]$ 满足 $i\not = j \And str[i]=str[j]$ 时,有:
$$dp[i][j]=min(dp[i+1][j],dp[i][j-1])$$
这里很难理解,说一下我的理解:
当 $i$ 和$j$ 颜色一样,即可以认为 $i$ 是涂 $[i+1,j]$ 的时候 顺便 涂上的,或者 $j$ 是涂 $[i,j-1]$ 的时候顺便涂上的。 又因为题目求最小值,所以取 $min$ 。
C++ 代码
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int ma=55;
int dp[ma][ma];//dp[i][j]:str[i]~str[j]的最少染色次数
char str[ma];
int main(void)
{
cin>>str+1;
int n=strlen(str+1);
memset(dp,0x3f,sizeof(dp));
for(register int i=1;i<=n;i++)
{
dp[i][i]=1;
}
for(register int len=1;len<=n;len++)
{
for(register int i=1,j=len+1;j<=n;i++,j++)
{
//i=1+1,j=len+1+1;
//i=1+1+1,j=len+1+1+1;
if(str[i]==str[j])
{
dp[i][j]=min(dp[i+1][j],dp[i][j-1]);//当i和j颜色一样——可以认为i是涂[i+1,j]的时候顺便涂上的,或者j是涂[i,j-1]的时候顺便涂上的。
}
else
{
for(register int k=i;k<j;k++)
{
dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]);
}
}
}
}
cout<<dp[1][n]<<endl;
return 0;
}