<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 {
public:
    int strangePrinter(string s) {
        // aaaabbbbaaaa
        // aaaabbbbaaaa
        // aaaabbbbbaaaa = aba
        // a  bcabdb
        // a  aaaaaa
        //
        // D(i, d, c) = min_{c2, k} (D(i, k, c2) + D(k + 1, d', c))
        // 100 * 100 * 26 * 100
        int n = s.size();
        vector<vector<array<int, 26>>> D(n + 1, vector<array<int, 26>>(n + 1));
        for (int d = 0; d <= n; ++d) {
            for (int i = 0; i < n; ++i) {
                for (int c = 0; c < 26; ++c) {
                    D[d][i][c] = d;
                    for (int dd = 1; dd <= d && i + dd <= n; ++dd) {
                        D[d][i][c] =
                            min(D[d][i][c], (s[i] - 'a' != c) +
                                                D[dd - 1][i + 1][s[i] - 'a'] +
                                                D[d - dd][i + dd][c]);
                    }
                }
            }
        }
        /*for (int d = 0; d <= n; ++d) {
            for (int i = 0; i < n; ++i) {
                for (int c = 0; c <= 1; ++c) {
                    std::cout << "d = " << d << " i = " << i << " c = " << c <<
        " --> " << D[d][i][c] << endl;
                }
            }
        }*/
        return equal(s.begin() + 1, s.end(), s.begin())
                   ? 1
                   : (D[n][0][s[0] - 'a'] + 1);
    }
};
// D[3][0][a] = D[0][1][a] + D[2][1][a]
//            = 0.         + 1 + D[0][2][b] + D[1][2][a]
//            = 0          + 1 + 0          + 0
66022