标签：min int 问题 55 涂色 区间 dp
- 一眼区间dp
- 设dp[i][j]为涂完i到j所需的最小次数
- 当a[i]==a[j]时，dp[i][j] = min(dp[i+1][j-1]+1,min(dp[i+1][j],dp[i][j-1]));
- 为什么是dp[i+1][j-1]+1,此时会产生一个异想天开的想法，就是取遍历一遍i+1到j-1这一段字符串，看是否有a[i]字符的出现，如果出现的话dp[i][j] = dp[i+1][j-1]，就是上来先把i到j这一段全涂成a[i]，然后去涂其他的，但这种做法不能保证在dp[i+1][j-1]-1的次数内正确涂满其余没涂的，例如，ABABA，dp[2][4] = 3,如果按照以上方法更新，dp[1][5] = 3,实际上dp[1][5] = 4。再来看dp[i][j-1]与dp[i+1][j]，在涂a[i]或a[j]时直接把i-j涂完，不会像前面一样影响答案。
- 当a[i]！=a[j]时，拆分区间就好
点击查看代码
#include<bits/stdc++.h>
using namespace std;
int n;
char a[55];
int dp[55][55];
int main(){
string s;
cin>>s; n = s.length();
for(int i = 1;i<=n;i++){
for(int j = 1;j<=n;j++) {
dp[i][j] = 51;
}
}
for(int i = 1;i<=s.length();i++){
a[i] = s[i-1];dp[i][i] = 1;
}
for (int i = 1; i <= n-1; i++) {
if(a[i]!=a[i+1]) dp[i][i+1] = 2;
else dp[i][i+1] = 1;
}
for (int len = 3; len <= n; len++) {
for (int i = 1; i + len - 1 <= n; i++) {
int j = i + len - 1;
if(a[i]==a[j]){
dp[i][j] = min(dp[i+1][j-1]+1,min(dp[i+1][j],dp[i][j-1]));
}
else{
for(int k = i;k<=j-1;k++){
// if(i==1&&j==3){
// cout<<dp[i][k]<<" "<<dp[k+1][j]<<" "<<dp[i][j]<<endl;
// }
dp[i][j] = min(dp[i][k]+dp[k+1][j],dp[i][j]);
}
}
}
}
cout<<dp[1][n];
}
标签：min,
int,
问题,
55,
涂色,
区间,
dp
From： https://www.cnblogs.com/wujw11world/p/17364725.html