blob: f4c41c800b1eda95813860106f32947ab4bd8ee7 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
|
#include "leetcode.h"
class Solution {
public:
int getLengthOfOptimalCompression(string s, int k) {
memset(dp, -1, sizeof(dp));
str = s, p = s.size();
return solve(0, k);
}
private:
const static int N = 127;
int dp[N][N], p;
string str;
inline int helper(int x) { return x == 1 ? 0 : x < 10 ? 1 : x < 100 ? 2 : 3; }
int solve(int left, int k) {
if (k < 0)
return N;
if (left >= p || p - left <= k)
return 0;
int &ans = dp[left][k];
if (ans != -1)
return ans;
ans = N;
int count[26] = {0};
for (int i = left, j = 0; i < p; i++) {
j = max(j, ++count[str[j] - 'a']);
ans = min(ans, 1 + helper(j) + solve(i + 1, k - (i - left + 1 - j)));
}
return ans;
}
};
int main() {
Solution obj;
cout << obj.getLengthOfOptimalCompression("aaabcccd", 2);
}
|