题目地址：http://vjudge.net/problem/UVALive-4394
很明显的区间DP
区间DP的套路就是 d[i][j]的在区间 (i,j) 刷的次数
转移也一般是 d[i][j]->d[i][k]+d[k+1][j]; 也就是一个区间分成两个区间
那么对于这道题就是想想怎么转移，也就是怎么将一个区间转移成两个区间
d[i][j]->d[i][k]+d[k+1][j];
1. if t[i]==t[j] ，也就是i刷到j
2. if t[i]==t[k+1] ，也就是i刷到k+1
3 if t[k]==t[j] ，也就是k刷到j
4. 什么也不干
还应该保存刷的颜色，所以多加一维paint
d[i][j][p] 就表示区间(i,j) 且刷了p的次数
#include <bits/stdc++.h>
using namespace std;
#define REP(i,a,b) for(int i=a;i<=(int)(b);++i)
#define REPD(i,a,b) for(int i=a;i>=(int)(b);--i)
const int INF=0x3f3f3f3f;
char s[100+5],t[100+5];
int d[100+5][100+5][35];
int DP(int i,int j,int paint){if(i>j) return 0;int& ans=d[i][j][paint];if(ans!=-1) return ans;if(i==j) {if(t[i]-'a'==paint||(paint==30&&t[i]==s[i])) return 0;else return 1;}ans=j-i+1;if(t[i]==t[j]) ans=min(ans,DP(i+1,j-1,t[i]-'a')+(paint!=t[i]-'a'));REP(k,i,j){if(t[i]==t[k]) ans=min(ans,DP(i+1,k-1,t[i]-'a')+DP(k+1,j,paint)+(paint!=t[k]-'a'));if(t[k]==t[j]) ans=min(ans,DP(i,k-1,paint)+DP(k+1,j-1,t[k]-'a')+(paint!=t[k]-'a'));ans=min(ans,DP(i,k,paint)+DP(k+1,j,paint)); //什么也不干} return ans;
}
int main(int argc, char const *argv[])
{while(scanf("%s%s",s+1,t+1)==2){memset(d,-1,sizeof(d));printf("%d\n", DP(1,strlen(s+1),30)); //一开始设一个不可能的值30}return 0;
}