leetcode

Solution to some Leetcode problems written in C++

git clone git://git.dimitrijedobrota.com/leetcode.git

1531.cpp (855B)

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];