leetcode

0 class Solution {

1 static int dp[127][127];

2

3 static int digits(int x) {

4 if (x == 1) return 0;

5 if (x < 10) return 1;

6 if (x < 100) return 2;

7 return 3;

8 }

9

10 public:

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

12 int getLengthOfOptimalCompression(const string &s, int k, int crnt = 0) const {

13 const int n = s.size();

14 if (k < 0) return n;

15 if (crnt >= n || n - crnt <= k) return 0;

16 if (dp[crnt][k] != -1) return dp[crnt][k];

17 int res = n, cnt[27] = {0};

18 for (int j = crnt, maxi = 0; j < n; j++) {

19 maxi = max(maxi, ++cnt[s[j] & 0x1F]);

20 res = min(res,

21 1 + digits(maxi) + getLengthOfOptimalCompression(s, k - (j - crnt + 1 - maxi), j + 1));

22 }

23 return dp[crnt][k] = res;

24 }

25 };

26

27 int Solution::dp[127][127];