String painter

#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <iostream>

using namespace std;

#define ll long long
#define inf 0x3f3f3f3f
ll dp[120][120], sum[120];
char a[120], b[120];

int main() {
    while (scanf("%s%s", a, b) != EOF) {
        int len = strlen(a);
        memset(dp, 0, sizeof(dp));
        for (int r = 0; r < len; r++) {
            for (int i = 0; i + r < len; i++) {
                int j = i + r;
                dp[i][j] = dp[i + 1][j] + 1;
                for (int k = i + 1; k <= j; k++) {
                    if (b[i] == b[k]) {
                        dp[i][j] = min(dp[i][j], dp[i + 1][k] + dp[k + 1][j]);
                    }
                }
            }
        }
        for (int i = 0; i < len; i++) {
            sum[i] = dp[0][i];
        }
        for (int i = 0; i < len; i++) {
            if (a[i] == b[i]) {
                if (i == 0) {
                    sum[i] = 0;
                } else {
                    sum[i] = sum[i - 1];
                }
            } else {
                for (int k = 0; k < i; k++) {
                    sum[i] = min(sum[i], sum[k] + dp[k + 1][i]);
                }
            }
        }
        printf("%d\n", sum[len - 1]);
    }
}