P4170 [CQOI2007] 涂色 区间 dp
P4170 [CQOI2007] 涂色
区间 dp 模板题，不理解为什么是蓝。
将现在考虑的区间 \([l,r]\) 分为 \([l,k]\) 和 \([k+1,r]\)，如果 \(s_l=s_r\) 就可以一起涂，少涂一次。
方程：
\[dp_{l,r}=\min_{k=l}^{r-1} dp_{l,k}+dp_{k+1,r}-[s_l=s_r]
\]
代码：
#include<bits/stdc++.h>
using namespace std;
char s[60];
int dp[60][60];
int n;
int dfs(int l,int r){
if(dp[l][r])return dp[l][r];
if(l==r)return dp[l][r]=1;
dp[l][r]=114514;
for(int k=l;k<r;k++){
dp[l][r]=min(dp[l][r],dfs(l,k)+dfs(k+1,r)-(s[l]==s[r]));
}
return dp[l][r];
}
int main(){
scanf("%s",s+1);
n=strlen(s+1);
cout<<dfs(1,n)<<endl;
return 0;
}