一、问题理解 行程长度编码(Run-Length Encoding)是一种简单有效的字符串压缩方法。题目要求我们在删除最多k个字符后,使压缩后的字符串长度最短。 二、解题思路三、关键代码解析初始化:处理空字符串的情况 双重循环:外层遍历字符串,内层遍历可能的删除次数 压缩成本计算:根据相同字符数量计算编码长度
四、完整代码
- class Solution {
- public:
- int getLengthOfOptimalCompression(string s, int k) {
- int n = s.size();
- // dp[i][j]表示前i个字符删除j个字符后的最小压缩长度
- vector<vector<int>> dp(n+1, vector<int>(k+1, INT_MAX/2));
-
- // 初始化:前0个字符删除j个字符的压缩长度为0
- for(int j = 0; j <= k; ++j) {
- dp[0][j] = 0;
- }
-
- for(int i = 1; i <= n; ++i) {
- for(int j = 0; j <= min(i, k); ++j) {
- // 情况1:删除当前字符
- if(j > 0) {
- dp[i][j] = dp[i-1][j-1];
- }
-
- // 情况2:保留当前字符
- int same = 0, diff = 0;
- // 向前查找相同字符,考虑删除不同字符的情况
- for(int m = i; m >= 1; --m) {
- if(s[m-1] == s[i-1]) {
- same++;
- } else {
- diff++;
- if(diff > j) break;
- }
-
- // 更新dp值
- int cost = 0;
- if(same == 1) cost = 1;
- else if(same < 10) cost = 2;
- else if(same < 100) cost = 3;
- else cost = 4;
-
- dp[i][j] = min(dp[i][j], dp[m-1][j-diff] + cost);
- }
- }
- }
-
- return dp[n][k];
- }
- };
复制代码
五、学习建议通过这道题,我们可以学习如何将复杂问题分解为子问题,并用动态规划高效解决。 来源:动态规划巧解字符串压缩优化问题 - 力扣1531题深度解析
|