LeetCode 1531题：动态规划解决字符串压缩

一、题目解读

LeetCode 1531题要求给定字符串s和整数k，返回通过删除最多k个字符后，能得到的最优压缩长度。

二、解题思路

用动态规划解决该问题。核心思想是将问题分解为子问题：计算前i个字符在删除j个字符后的最短压缩长度。关键在于定义状态和状态转移方程，同时考虑字符删除与保留的权衡。

三、解题步骤

1. 状态定义：创建二维dp数组dp[i][j]，表示前i个字符删除j个字符后的最小压缩长度。

2. 初始化：dp[0][j]=0（前0个字符的压缩长度为0）。

3. 状态转移：

    情况1（删除当前字符）：若j>0，可直接继承前i-1个字符删除j-1个字符的结果，即dp[i][j] = dp[i-1][j-1]。

    情况2（保留当前字符）：向前查找连续相同字符段，统计相同字符数（same）与不同字符数（diff）。当diff超过j时停止（因删除数受限），计算压缩成本（根据字符计数长度：1个字符为1，2-9个为2，10-99为3，≥100为4）。通过dp[m-1][j-diff]（前m-1个字符删除j-diff个字符）转移并更新最小压缩长度。

4. 最终结果：dp[n][k]即为整个字符串在删除k个字符后的最优压缩长度。

四、代码与注释

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

五、总结

该解法通过动态规划巧妙地将问题转化为子问题求解，时间复杂度为O(n²k)，空间复杂度为O(nk)。核心难点在于状态转移时平衡删除与保留字符的策略，并通过分段计数优化压缩成本计算。适用于需要高效处理字符串压缩与删除限制的场景，为同类问题提供了经典解题思路。