/*
 * @lc app=leetcode.cn id=664 lang=cpp
 *
 * [664] 奇怪的打印机
 */

// @lc code=start
class Solution {
    const int INF = 0x3f3f3f3f;

public:
    int f[110][110];
    int strangePrinter(string s) {
        int n = s.size();

        memset(f, 0x3f, sizeof f);
        for (int i = n - 1; i >= 0; i--) {
            f[i][i] = 1;

            for (int j = i + 1; j < n; j++) {
                if (s[i] == s[j])
                    f[i][j] = f[i][j - 1];
                else {
                    for (int k = i; k < j; k++)
                        f[i][j] = min(f[i][j], f[i][k] + f[k + 1][j]);
                }
            }
        }
        return f[0][n - 1];
    }
};
// @lc code=end