动态规划巧解字符串压缩优化问题 - 力扣1531题深度解析

rhsgfswg

一、问题理解

行程长度编码(Run-Length Encoding)是一种简单有效的字符串压缩方法。题目要求我们在删除最多k个字符后，使压缩后的字符串长度最短。

二、解题思路

• 动态规划状态定义：
  dp[j]表示前i个字符删除j个字符后的最小压缩长度

• 状态转移：

  
  

• 情况1：删除当前字符，直接继承dp[i-1][j-1]
• 情况2：保留当前字符，向前查找相同字符序列，计算保留这些字符的压缩成本
  
  

三、关键代码解析

• 初始化：处理空字符串的情况
• 双重循环：外层遍历字符串，内层遍历可能的删除次数
• 压缩成本计算：根据相同字符数量计算编码长度
  
  

四、完整代码

1. class Solution {
   
2. public:
   
3. int getLengthOfOptimalCompression(string s, int k) {
   
4. int n = s.size();
   
5. // dp[i][j]表示前i个字符删除j个字符后的最小压缩长度
   
6. vector<vector<int>> dp(n+1, vector<int>(k+1, INT_MAX/2));
   
7. 
   
8. // 初始化：前0个字符删除j个字符的压缩长度为0
   
9. for(int j = 0; j <= k; ++j) {
   
10. dp[0][j] = 0;
    
11. }
    
12. 
    
13. for(int i = 1; i <= n; ++i) {
    
14. for(int j = 0; j <= min(i, k); ++j) {
    
15. // 情况1：删除当前字符
    
16. if(j > 0) {
    
17. dp[i][j] = dp[i-1][j-1];
    
18. }
    
19. 
    
20. // 情况2：保留当前字符
    
21. int same = 0, diff = 0;
    
22. // 向前查找相同字符，考虑删除不同字符的情况
    
23. for(int m = i; m >= 1; --m) {
    
24. if(s[m-1] == s[i-1]) {
    
25. same++;
    
26. } else {
    
27. diff++;
    
28. if(diff > j) break;
    
29. }
    
30. 
    
31. // 更新dp值
    
32. int cost = 0;
    
33. if(same == 1) cost = 1;
    
34. else if(same < 10) cost = 2;
    
35. else if(same < 100) cost = 3;
    
36. else cost = 4;
    
37. 
    
38. dp[i][j] = min(dp[i][j], dp[m-1][j-diff] + cost);
    
39. }
    
40. }
    
41. }
    
42. 
    
43. return dp[n][k];
    
44. }
    
45. };

复制代码

五、学习建议

• 先理解基础RLE算法
• 练习简单DP问题
• 逐步过渡到这类复杂DP问题
  
  

通过这道题，我们可以学习如何将复杂问题分解为子问题，并用动态规划高效解决。

来源：竞赛学习