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

深度学习
• 阅读 3

动态规划巧解字符串压缩优化问题 - 力扣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问题

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

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

点赞
收藏
评论区
推荐文章
DaLongggggg DaLongggggg
4年前
python百题大冲关-压缩字符串
挑战介绍实现一个算法来压缩一个字符串。压缩的要求如下:需要判断压缩能不能节省空间,仅在压缩后字符串比原字符串长度更短时进行压缩。压缩的格式是将连续相同字符替换为字符数字形式,例如"AAABCCDDDD"变为"A3BC2D4"。本次挑战中,你需要在compress_str.py文件中补充函数compress的空缺部分
Stella981 Stella981
3年前
Leetcode 424.替换后的最长重复字符
替换后的最长重复字符给你一个仅由大写英文字母组成的字符串,你可以将任意位置上的字符替换成另外的字符,总共可最多替换 _k_次。在执行上述操作后,找到包含重复字母的最长子串的长度。注意:字符串长度和_k_不会超过 104。示例1:输入:s"ABAB",k2输
贾蔷 贾蔷
1个月前
力扣501题 解题思路和步骤 C++代码实现,力扣(leetcode)
问题背景及描述力扣501题要求我们找出在一个二叉搜索树(BST)中的众数。二叉搜索树是一种特殊的二叉树,其中每个节点的值都大于其左子树中的任何节点,且小于其右子树中的任何节点。众数是指在BST中出现次数最多的值。解题思路分析解题的关键在于理解BST的性质以
贾蔷 贾蔷
3星期前
蓝桥杯2023接龙数列(洛谷P9242)题解:动态规划与数字首尾匹配的完美应用
一、题目解读这道蓝桥杯省赛真题要求找出数字序列中最长的接龙子序列(每个数字的首位等于前一个数字的末位),并计算需要删除的最少数字个数。题目考察动态规划的实际应用能力,是理解数字特征处理和状态转移的典型案例。二、解题步骤1.处理n1的特殊边界情况2.读取输入
贾蔷 贾蔷
3星期前
2025年GESP七级等价消除(洛谷P11965)代码解析与优化策略
一、题目解读2025年GESP七级考试中的“等价消除(洛谷P11965)”问题要求统计给定字符串中满足等价条件的子串数量。所谓“等价子串”,是指子串中所有字符出现的次数均相同。题目需要高效算法解决,考验对字符串处理和状态压缩的掌握。二、解题思路采用位运算
深度学习 深度学习
1星期前
2024蓝桥杯省赛B组前缀总分(洛谷P12124)解题思路与代码详解
一、题目解读2024年蓝桥杯省B组题目“前缀总分”(对应洛谷P12124)要求计算给定字符串集合中,所有前缀的最长公共前缀(LCP)的总分,并找出通过移动字符位置后可能获得的最大总分。题目考察字符串处理与动态规划能力,需高效计算LCP并优化得分策略。二、解
深度学习 深度学习
1星期前
洛谷P2034题解:动态规划+单调队列优化求解最大K段子段和问题
一、题目解读洛谷P2034题目要求给定一个长度为n的整数数组,将其分成不超过k段,求各段和的最大值。该问题属于经典动态规划问题的扩展,需结合优化技巧高效求解。二、解题思路采用动态规划单调队列优化的策略。核心思想是定义状态dp
贾蔷 贾蔷
1星期前
棋盘翻转大师:力扣LCP41题"翻转黑白棋"深度解析
截图未命名.jpg棋盘翻转大师:力扣LCP41题"翻转黑白棋"深度解析递归算法方向向量力扣LCP41C第1张一、问题理解题目要求在一个黑白棋棋盘上找出一个空位('.'表示),当放置一个黑棋('X')后,能够翻转最多数量的白棋('O')。翻转规则遵循标准
贾蔷 贾蔷
4小时前
动态规划预处理+滑动窗口:力扣2420题"好下标"解法详解
一、问题理解题目要求找出中满足特定条件的"好下标":对于下标i,其左侧k个元素必须是非递增的,右侧k个元素必须是非递减的。这是典型的数组区间性质检查问题。二、解题思路1.预处理核心思想是通过两次预处理:left数组:记录每个位置向左的非长度right数组:
贾蔷 贾蔷
1个月前
力扣1137题 解题思路和步骤 C++代码实现,力扣一共多少题
一、题目分析力扣1137题要求我们找到第N个泰波那契数。泰波那契数的定义是:T00,T11,T21,且在n0的条件下Tn3TnTn1Tn2。,当n4时,T4T3T2T14。这道题主要考查我们对递归或动态规划的理解和运用。在思考解题方法时,我们