查看: 14|回复: 0

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

[复制链接]
  • TA的每日心情
    擦汗
    11 小时前
  • 签到天数: 37 天

    [LV.5]常住居民I

    36

    主题

    0

    回帖

    67

    积分

    注册会员

    Rank: 2

    积分
    67
    发表于 11 小时前 | 显示全部楼层 |阅读模式
    一、问题理解

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

    二、解题思路
    • 情况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问题

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

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


    回复

    使用道具 举报

    您需要登录后才可以回帖 登录 | 立即注册

    本版积分规则

    快速回复 返回顶部 返回列表