一、问题理解
行程长度编码(Run-Length Encoding)是一种简单有效的字符串压缩方法。题目要求我们在删除最多k个字符后,使压缩后的字符串长度最短。
二、解题思路
- 情况1:删除当前字符,直接继承dp[i-1][j-1]
- 情况2:保留当前字符,向前查找相同字符序列,计算保留这些字符的压缩成本
三、关键代码解析
- 初始化:处理空字符串的情况
- 双重循环:外层遍历字符串,内层遍历可能的删除次数
- 压缩成本计算:根据相同字符数量计算编码长度
四、完整代码
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];
}
};
五、学习建议
- 先理解基础RLE算法
- 练习简单DP问题
- 逐步过渡到这类复杂DP问题
通过这道题,我们可以学习如何将复杂问题分解为子问题,并用动态规划高效解决。