664. Strange Printer

There is a strange printer with the following two special properties:

• The printer can only print a sequence of the same character each time.
• At each turn, the printer can print new characters starting from and ending at any place and will cover the original existing characters.

Given a string s, return the minimum number of turns the printer needed to print it.

• Time : O(n^2)
• Space : O(n^2)

c++

class Solution {
    int dp[101][101];
    int solution(string& s, int l, int r) {
        if(l == r) return 1;
        if(l + 1 == r) return s[l] == s[r] ? 1 : 2;
        if(dp[l][r] != -1) return dp[l][r];
        dp[l][r] = r - l + 1;
        for(int i = l; i < r; i++) {
            dp[l][r] = min(dp[l][r], solution(s,l,i) + solution(s,i+1,r) + (s[i] == s[r] ? -1 : 0));
        }
        return dp[l][r];
    }
public:
    int strangePrinter(string s) {
        s.erase(unique(s.begin(), s.end()), s.end());
        memset(dp, -1, sizeof(dp));
        return solution(s, 0, s.length()-1);
    }
};