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

一、问题理解

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

二、解题思路

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

2. 状态转移：

• 情况1：删除当前字符，直接继承dp[i-1][j-1]

• 情况2：保留当前字符，向前查找相同字符序列，计算保留这些字符的压缩成本

三、关键代码解析

1. 初始化：处理空字符串的情况

2. 双重循环：外层遍历字符串，内层遍历可能的删除次数

3. 压缩成本计算：根据相同字符数量计算编码长度

四、完整代码

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];
    }
};

五、学习建议

1. 先理解基础RLE算法

2. 练习简单DP问题

3. 逐步过渡到这类复杂DP问题

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