<p>There is a strange printer with the following two special properties:</p>

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

<p>Given a string <code>s</code>, return <em>the minimum number of turns the printer needed to print it</em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;aaabbb&quot;
<strong>Output:</strong> 2
<strong>Explanation:</strong> Print &quot;aaa&quot; first and then print &quot;bbb&quot;.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;aba&quot;
<strong>Output:</strong> 2
<strong>Explanation:</strong> Print &quot;aaa&quot; first and then print &quot;b&quot; from the second place of the string, which will cover the existing character &#39;a&#39;.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= s.length &lt;= 100</code></li>
	<li><code>s</code> consists of lowercase English letters.</li>
</ul>

class Solution {
private:
    int rec(int st, int ed, int mode, vector<vector<vector<int> > > &dp, string &s) {
        // MODE
        // 0 -> normal
        // 1 -> exploration

        if (dp[st][ed][mode] != -1) {
            return dp[st][ed][mode];
        }
        
        if (mode == 0) {
            if (st == ed) {
                return dp[st][ed][mode] = 1;
            }
            
            if (st + 1 == ed) {
                return dp[st][ed][mode] = 1 + int(s[st] != s[ed]);
            }

            int res = INT_MAX;
            
            // split
            for (int i = st; i <= ed-1; i++) {
                res = min(res, rec(st, i, 0, dp, s) + rec(i+1, ed, 0, dp, s));
            }

            if (s[st] == s[ed]) {
                res = min(res, rec(st, ed, 1, dp, s) + 1);
            }

            // no split
            res = min(res, 1 + rec(st+1, ed, 0, dp, s));
            res = min(res, 1 + rec(st, ed-1, 0, dp, s));

            return dp[st][ed][mode] = res;
        } else {
            // mode == 1

            assert(s[st] == s[ed]);
            
            int res = INT_MAX;

            // no exploration
            res = min(res, rec(st+1, ed-1, 0, dp, s));

            // explor
            for (int i = st+1; i <= ed-1; i++) {
                if (s[st] == s[i]) {
                    res = min(res, rec(st+1, i-1, 0, dp, s) + rec(i, ed, 1, dp, s));
                }
            }

            return dp[st][ed][mode] = res;
        }
        
        
    }

public:
    int strangePrinter(string s) {
        string smin;
        smin.reserve(s.length());

        smin += s[0];
        for (int i = 1; i < s.length(); i++) {
            if (s[i] != s[i-1]) {
                smin += s[i];
            }
        }

        vector<vector<vector<int> > > dp(smin.length());
        for (int i = 0; i < smin.length(); i++) {
            dp[i].resize(smin.length());
            for (int j = 0; j < smin.length(); j++) {
                dp[i][j].resize(2, -1);
            }
        }

        // cout << smin << "\n";
        
        return rec(0, int(smin.length())-1, 0, dp, smin);
    }
};
34697