染色PAINT

题目大意：给出目标字符串，然后从空串开始涂色，每次可以任意选择一个区间涂，问最少次数。

解题思路：

区间dp问题，开一个二维dp数组，dp[i][j] 代表区间从 i 到 j 最小染色次数。

如果区间两端颜色相同 s[i]==s[j] 的话，dp[i][j]=min(dp[i][j-1],dp[i+1][j]) 。

颜色不同 s[i] !=s [j]的话 ，枚举中间端点k，把此区间分为两部分，转换为子问题求解即可。

Code:

[code]#include <iostream>#include <cstdio>#include <cmath>#include <queue>#include <cstring>#include <algorithm>#include <vector>#include <set>#include <map>#define inf 0x3f3f3f3fusing namespace std;typedef long long int ll;const int maxn=1e2+7;int dp[maxn][maxn];int main(){ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);string s;cin>>s;int len=s.length();s=\' \'+s;memset(dp,inf,sizeof dp);for(int i=1;i<=len;i++) dp[i][i]=1;for(int z=2;z<=len;z++){for(int i=1;i+z-1<=len;i++){int j=i+z-1;if(s[i]==s[j]) dp[i][j]=min(dp[i+1][j],dp[i][j-1]);else{for(int k=i;k<j;k++){dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]);}}}}cout<<dp[1][len]<<endl;return 0;}