动态规划巧解字符串压缩优化问题 - 力扣1531题深度解析
https://dajuwangluo.cn/zb_users/upload/2025/07/202507061751788072253509.jpg一、问题理解行程长度编码(Run-Length Encoding)是一种简单有效的字符串压缩方法。题目要求我们在删除最多k个字符后，使压缩后的字符串长度最短。二、解题思路[*]动态规划状态定义：
dp表示前i个字符删除j个字符后的最小压缩长度
[*]状态转移：
[*]情况1：删除当前字符，直接继承dp
[*]情况2：保留当前字符，向前查找相同字符序列，计算保留这些字符的压缩成本
三、关键代码解析
[*]初始化：处理空字符串的情况
[*]双重循环：外层遍历字符串，内层遍历可能的删除次数
[*]压缩成本计算：根据相同字符数量计算编码长度
四、完整代码
class Solution {
public:
int getLengthOfOptimalCompression(string s, int k) {
int n = s.size();
// dp表示前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;
}
for(int i = 1; i <= n; ++i) {
for(int j = 0; j <= min(i, k); ++j) {
// 情况1：删除当前字符
if(j > 0) {
dp = dp;
}
// 情况2：保留当前字符
int same = 0, diff = 0;
// 向前查找相同字符，考虑删除不同字符的情况
for(int m = i; m >= 1; --m) {
if(s == s) {
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 = min(dp, dp + cost);
}
}
}
return dp;
}
};
五、学习建议
[*]先理解基础RLE算法
[*]练习简单DP问题
[*]逐步过渡到这类复杂DP问题
通过这道题，我们可以学习如何将复杂问题分解为子问题，并用动态规划高效解决。来源：动态规划巧解字符串压缩优化问题 - 力扣1531题深度解析
页:
[1]