HDU - 2476 String painter（区间DP）

HDU - 2476 String painter

题目要求：将一串字符串A改成一串字符串B，每次修改只能修改一定区间内的，问最少几次能够完成。

给大家模拟一下第一组样例

0~10：变成a，aaaaaaaaaaa

1~9：变成b，babbbbbbbbba

2~8：变成c，abcccccccba

3~7：变成d，abcdddddcba

4~6：变成e，abcdeeedcab

5：变成f，abcdefedcab

一种需要6次，所以说应该用区间DP来解决此类问题

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;const int N = 110;
char a[N],b[N];
int s[N],dp[N][N];int main()
{
    while(scanf("%s%s",a,b)!=EOF){
    memset(dp,0,sizeof dp);int l=strlen(a);for(int i=0;i<l;i++) dp[i][i]=1;for(int len=1;len<l;len++)for(int i=0;i<l-len;i++){
    int j=i+len;dp[i][j]=dp[i+1][j]+1;for(int k=i+1;k<=j;k++)if(b[i]==b[k])dp[i][j]=min(dp[i][j],dp[i+1][k]+dp[k+1][j]);}for(int i=0;i<l;i++) s[i]=dp[0][i];for(int i=0;i<l;i++){
    if(a[i]==b[i]) s[i]=s[i-1];for(int j=0;j<i;j++) s[i]=min(s[i],s[j]+dp[j+1][i]);}printf("%d\n",s[l-1]);}return 0;
}