hdu 2476 String Painter

第一道区间dp题，感觉题意不是很好理解

题意：一次可以转换某一个位置的字符，或是一串连续的字符，举第一个例子zzzzzfzzzzz

1：aaaaaaaaaaa

2: abbbbbbbbba

3: abcccccccba

4: abcdddddcba

5: abcdeeedcba

6: abcdefedcba

于是第一个例子输出6，第二个同理

话不多说，直接贴一波代码

#include<cstdio>  
#include<iostream>  
#include<algorithm>
#include<math.h> 
#include<string.h>  
#include<vector> 
#include<queue>
#include<map>
#include<iterator>
#include<vector>
#include<set>
#define INF 9999999
typedef long long ll;
const int Max=(1<<16)+10;
using namespace std;

int dp[1005][1005];//dp[i][j]表示从i~j的刷法 
int ans[1005]; 

int main()
{
    string str1,str2;
    int len;
    while(cin>>str1>>str2)
    {
        len=str1.length();
        for(int j=0;j<len;j++)
        {
            for(int i=j;i>=0;i--) 
            {
                dp[i][j]=dp[i+1][j]+1;//逐个更新区间i~j内的值 
                for(int k=i+1;k<=j;k++)
                {
                    if(str2[i]==str2[k])//若遇到相同的则需寻找区间的最小值 
                        dp[i][j]=min(dp[i][j],dp[i+1][k]+dp[k+1][j]);
                } 
            }
        }
        
        for(int i=0;i<len;i++)
            ans[i]=dp[0][i];//ans[i]表示区间[0,i]需要刷的值 
        for(int i=0;i<len;i++)
        {
            if(str1[i]==str2[i])//碰到相同的值选择不刷 
                ans[i]=ans[i-1];
            else
            {
                for(int j=0;j<i;j++)//寻找最优解 
                    ans[i]=min(ans[i],ans[j]+dp[j+1][i]);
            }
        }    
        cout<<ans[len-1]<<endl;
    }
    return 0;
}