<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:
    // string pref = " ";
    vector<vector<int>> memo;
    int count_moves(int b, int e, string &s) {
        // cout << pref << "1* " << b << ',' << e <<'\n';
        struct DP {
            int e;
            int min_turns;
        };
        if (b > e) return 0;
        if (b == e) return 1;
        if (s[b] == s[e]) --e; // we can print e with b
        // cout << pref << "2* " << b << ',' << e <<'\n';
        if (memo[b][e] != -1) return memo[b][e];
        // cout << pref << "3* " << b << ',' << e <<'\n';
        vector<DP> dps(0);
        for (int ib=b+1, ie=ib; ie<=e+1; ++ie) {
            if (ie == e+1 || s[b] == s[ie]) {
                // cout << pref << "i:" << ib << ',' << ie-1 << '\n';
                // cout << pref << "; s:" << s[ib] << ',' << s[ie-1] << '\n';
                // [ib,ie) is a new interval - find best way to print [b+1, ie);
                // pref += "  ";
                DP new_dp{ie-1, count_moves(b+1, ie-1, s)};
                for (auto dp: dps) {
                    int sub_turns = count_moves(dp.e+2, ie-1, s);
                    new_dp.min_turns = min( new_dp.min_turns, 
                                            dp.min_turns + sub_turns);
                    // cout << pref << ". " << dp.e+2 <<',' << ie-1 << "->" << dp.min_turns << '+' << sub_turns << '\n';
                }
                // pref.pop_back();
                // pref.pop_back();
                dps.push_back(new_dp);
                ib = ie+1;
            }
        }
        ++dps.back().min_turns;
        // cout << pref << "E* " << b << ',' << e << '-' << dps.back().min_turns << '\n';
        return memo[b][e] = dps.back().min_turns;

    }
public:
    int strangePrinter(string s) {
        string s0;
        int n = s.size();
        for(int b=0,e=0; e<n; ++e) {
            if(s[b] != s[e]) {
                s0.push_back(s[b]);
                b = e;
            }
        }
        s0.push_back(s[n-1]);
        // cout << s0 << '\n';
        n = s0.size();
        memo = vector<vector<int>>(n, vector<int>(n, -1));
        

        return count_moves(0, n-1, s0);
    }
};
26642