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;
}
