leetcode

0 class Solution {

1 int dp[101][101];

2 int rec(const string &s, int l, int r) {

3 if (dp[l][r] != -1) return dp[l][r];

4 int res = s.size(), j = -1;

5 for (int i = l; i < r; i++) {

6 if (s[i] != s[r] && j == -1) j = i;

7 if (j != -1) res = min(res, 1 + rec(s, j, i) + rec(s, i + 1, r));

8 }

9 return dp[l][r] = j != -1 ? res : 0;

10 }

11

12 public:

13 Solution() { memset(dp, 0xFF, sizeof(dp)); }

14 int strangePrinter(string &s) {

15 int j = 1;

16 for (int i = 1; i < s.size(); i++)

17 if (s[i] != s[i - 1]) s[j++] = s[i];

18

19 return rec(s, 0, j - 1) + 1;

20 }

21 };