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

胡志明t

一、问题理解

行程长度编码(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问题
  
  

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

来源：竞赛学习