【题目链接】 

 

【题目大意】

　　假设你有一条长度为n的木版，初始时没有涂过任何颜色

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

　　求最少的涂色次数达到目标状态

 

【题解】

　　dp[i][j]表示涂抹i到j的最优答案，

　　显然当i和j相同时，可以从i+1……j,i……j-1,i+1……j-1转移过来，

　　同时也可以从两个区间组合得到。

 

【代码】

#include 
     
      #include 
      
       #include 
       
        using namespace std;const int N=100;int dp[N][N];char s[N];int main(){    while(~scanf("%s",s+1)){        int n=strlen(s+1);        memset(dp,0x3f,sizeof(dp));        for(int i=1;i<=n;i++)dp[i][i]=1;        for(int k=1;k