区间DP,dp[i][j][k]表示染色区间i,j当前颜色为k(0,表示无色)的最小代价,然后记忆化搜索进行转移即可
代码:
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int N = 105; const int INF = 0x3f3f3f3f; char a[N], b[N]; int dp[N][N][N], n; int dfs(int l, int r, int c) { int &ans = dp[l][r][c]; if (ans != -1) return ans; ans = INF; if (l > r) return ans = 0; if (!c && a[l] == b[l]) ans = min(ans, dfs(l + 1, r, c)); if (c && b[c] == b[l]) ans = min(ans, dfs(l + 1, r, c)); for (int i = l; i <= r; i++) ans = min(ans, dfs(l + 1, i, l) + dfs(i + 1, r, c) + 1); return ans; } int main() { while (gets(a + 1) != NULL) { gets(b + 1); n = strlen(a + 1); memset(dp, -1, sizeof(dp)); printf("%d\n", dfs(1, n, 0)); } return 0; }