1
class Solution {
2
 public:
3
  int dp[101][101];
4
  int dfs(string &s, int left, int K) {
5
    int k = K;
6
    if (s.size() - left <= k) return 0;
7
    if (dp[left][k] >= 0) return dp[left][k];
8
    int res = k ? dfs(s, left + 1, k - 1) : 10000, c = 1;
9
    for (int i = left + 1; i <= s.size(); ++i) {
10
      res = min(res, dfs(s, i, k) + 1 + (c >= 100 ? 3 : (c >= 10 ? 2 : (c > 1 ? 1 : 0))));
11
      if (i == s.size()) break;
12
      if (s[i] == s[left])
13
        ++c;
14
      else if (--k < 0)
15
        break;
16
    }
17
    return dp[left][K] = res;
18
  }
19

20
  int getLengthOfOptimalCompression(string s, int k) {
21
    memset(dp, -1, sizeof(dp));
22
    return dfs(s, 0, k);
23
  }
24
};