<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>

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef pair<double, double> pdd;
#define pb push_back
#define mp make_pair
#define fs first
#define sc second
#define rep(i, from, to) for (int i = from; i < (to); ++i)
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()
#define FOR(i, to) for (int i = 0; i < (to); ++i)
typedef vector<vector<int> > vvi;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<pair<int, int> > vpi;
typedef pair<ll,ll> pll;
typedef vector<string> vs;

int dp[110][110];

class Solution {
public:
    int strangePrinter(string t) {
        string s;
        FOR(i, sz(t)) {
            if(!i || t[i] != t[i-1]) s.pb(t[i]);
        }
        int N = sz(s);
        FOR(i,N) {
            rep(j, i, N) {
                dp[i][j] = j-i+1;
            }
        }

        for(int len=2;len<=N;++len) {
            FOR(l, N-len+1) {
                int r = l + len - 1;

                vi ind;
                for(int k=l;k<r;++k) {
                    if(s[k]==s[l]) ind.pb(k);
                    dp[l][r] = min(dp[l][r], dp[l][k] + dp[k+1][r]);
                }
                if(s[l] != s[r]) continue;
                ind.pb(r);

                vi bst; bst.resize(sz(ind), N);
                bst[0] = 0;
                FOR(i, sz(ind)) {
                    FOR(j, i) {
                        bst[i] = min(bst[i], bst[j] + dp[ind[j]+1][ind[i]-1]);
                    }
                }

                dp[l][r] = min(dp[l][r], 1 + bst.back());
            }
        }
        return dp[0][N-1];
    }
};
26642