664. Strange Printer

https://leetcode.com/problems/strange-printer/description/

打印机每次能在任意位置输出任意长度的连续的字符串，问打出给定的字符串至少需要输出几次。字符串+优化 => DP。对于末尾为S[j]的字符串，它可能是j之前任意与S[j]相同的字符k开始往后print的产物，因此问题可以缩小成更小的此问题。所以本质是一个划分问题，action为选择不同的k作为生成S[j]的打印操作，dp[k][j]存打印出S[k:j]所需最少次数。

思路参考自花花。

/*
 * @lc app=leetcode id=664 lang=cpp
 *
 * [664] Strange Printer
 */

// @lc code=start
class Solution {
public:
    int strangePrinter(string s) {
        const int N = s.size();
        if (N == 0) return 0;
        vector<vector<int>> dp(N + 1, vector<int>(N + 1, 0));
        for (int i = 0; i <= N; ++i) dp[i][i] = 1;
        for (int i = N; i > 0; --i) { 
            for (int j = i + 1; j <= N; ++j) {
                dp[i][j] = dp[i][j - 1] + 1;
                for (int k = i; k < j; ++k) {
                    if (s[k - 1] == s[j - 1]) {
                        dp[i][j] = min(dp[i][j], dp[i][k - 1] + dp[k][j - 1]);
                    }
                }
            }
        }
        return dp[1][N];
        // return dfs(s, dp, 0, N - 1);
    }

    int dfs(string &s, vector<vector<int>> &dp, int i, int j) {
        if (j < i) return 0;
        if (dp[i][j] != INT_MAX) return dp[i][j];
        dp[i][j] = dfs(s, dp, i, j - 1) + 1;
        for (int k = i; k < j; ++k) {
            if (s[k] == s[j]) {
                dp[i][j] = min(dp[i][j], dfs(s, dp, i, k - 1) + dfs(s, dp, k, j - 1));
            }
        }
        return dp[i][j];
    }
};
// @lc code=end