Home LeetCode-664 Strange Printer
Post
Cancel

LeetCode-664 Strange Printer

Description

TL;DR 粉刷匠

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

Constraints

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

Solution

区间DP即可

Code

class Solution {
public:
    int strangePrinter(string s) {
        int dp[102][102];
        memset(dp, 0x3f, sizeof dp);
        for(int i = 0; i < s.size(); ++i) dp[i][i] = 1;
        for(int l = s.size()-1; ~l; --l) {
            for(int r = l + 1; r < s.size(); ++r) {
                // Note
                if(s[l] == s[r]) dp[l][r] = min(dp[l][r-1], dp[l+1][r]);

                for(int pos = l; pos < r; ++pos) {
                    dp[l][r] = min(dp[l][r], dp[l][pos] + dp[pos+1][r]);
                }
            }
        }
        return dp[0][s.size()-1];
    }
};

LeetCode-664 Strange Printer

This post is licensed under CC BY 4.0 by the author.
Contents