1
class Solution {
2
 public:
3
  int dp[101][101];
4
  int solve(string s, int i, int j) {
5
    if (i > j) return 0;
6
    if (dp[i][j] != -1) return dp[i][j];
7
    int ans = 0;
8
    while (i < j && s[i + 1] == s[i]) i++;
9
    while (i < j && s[j] == s[j - 1]) {
10
      j--;
11
    }
12
    ans = 1 + solve(s, i + 1, j);
13
    for (int k = i + 1; k <= j; k++) {
14
      if (s[k] == s[i]) {
15
        int cnt = solve(s, i + 1, k - 1) + solve(s, k, j);
16
        ans = min(ans, cnt);
17
      }
18
    }
19
    return dp[i][j] = ans;
20
  }
21
  int strangePrinter(string s) {
22
    memset(dp, -1, sizeof(dp));
23
    return solve(s, 0, s.size() - 1);
24
  }
25
};
26
// if you like the solution plz upvote.