Description

TL;DR 粉刷匠

给定一个字符串\(s\)和空串\(t\),每次操作可以覆盖任意连续长度的字符,但必须是相同字符。求从\(t\)串到\(s\)串的最少操作次数

Constraints

\(s\)长度不超过\(100\)

Solution

区间DP即可

Code

class Solution {
public:
    int strangePrinter(string s) {
        int dp[103][103];
        memset(dp, -1, sizeof dp);
        constexpr static int BAD = 1<<20;
        auto DP = [&](auto &&DP, int l, int r) -> int {
            if(l == r) return 1;
            if(l > r) return BAD;
            if(~dp[l][r]) return dp[l][r];
            int ans = BAD;
            if(s[l] == s[r]) ans = min(DP(DP, l+1, r), DP(DP, l, r-1));
            for(int p = l; p < r; p++) {
                ans = min(ans, DP(DP, l, p) + DP(DP, p+1, r));
            }
            return dp[l][r] = ans;
        };
        return DP(DP, 0, s.size() - 1);
    }
};

LeetCode-664 Strange Printer