【区间 DP】运用区间 DP 解决古老原题

这篇具有很好参考价值的文章主要介绍了【区间 DP】运用区间 DP 解决古老原题。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

题目描述

这是 LeetCode 上的 「664. 奇怪的打印机」 ,难度为 「困难」

Tag : 「区间 DP」

有台奇怪的打印机有以下两个特殊要求:

  • 打印机每次只能打印由 同一个字符 组成的序列。
  • 每次可以在任意起始和结束位置打印新字符,并且会覆盖掉原来已有的字符。

给你一个字符串 s ,你的任务是计算这个打印机打印它需要的最少打印次数。

示例 1:

输入:s = "aaabbb"

输出:2

解释:首先打印 "aaa" 然后打印 "bbb"

示例 2:

输入:s = "aba"

输出:2

解释:首先打印 "aaa" 然后在第二个位置打印 "b" 覆盖掉原来的字符 'a'

提示:

  • s 由小写英文字母组成

基本分析

首先,根据题意我们可以分析出一个重要推论:连续相同的一段字符,必然可以归到同一次打印中,而不会让打印次数变多。注意,这里说的是「归到一次」,而不是说「单独作为一次」

怎么理解这句话呢?

举个 🌰,对于诸如 ...bbaaabb... 的样例数据,其中多个连续的 a 必然可以归到同一次打印中,但这一次打印可能只是将 aaa 作为整体进行打印;也有可能是 aaa 与前面或者后面的 a 作为整体被打印(然后中间的 b 被后来的打印所覆盖)。但无论是何种情况连续一段的 aaa 必然是可以「归到同一次打印」中。

我们可以不失一般性证明「连续相同的一段字符,必然可以归到同一次打印中,而不会让打印次数变多」这个推理是否正确:

假设有目标序列 其中 连续一段字符相同,假如这一段的打印被最后完成(注意最后完成不代表这一段要保留空白,这一段可以此前被打印多次),除了这一段以外所消耗的打印次数为 ,那么根据 不同的打印方案有:

  1. 单纯划分为多段:总共打印的次数大于 (此方案不会取到打印最小值 ,可忽略)
  2. 归到同一次打印:总共打印的次数等于
  3. 结合之前的打印划分为多段,即 一段的两段本身就是「目标字符」,我们本次只需要打印 中间的部分。总共打印的次数等于

由于同样的地方可以被重复打印,因此我们可以将情况 中打印边缘扩展到 处,这样最终打印结果不变,而且总的打印次数没有增加。

到这一步,我们其实已经证明出「连续相同的一段字符,必然可以归到同一次打印中,而不会让打印次数变多」的推论成立了。

但可能会有同学提出疑问:怎么保证 是被最后涂的?怎么保证 不是和其他「不相邻的同样字符」一起打印的?

答案是不用保证,因为不同状态(打印结果)之间相互独立,而有明确的最小转移成本。即从当前打印结果 a 变成打印结果 b,是具有明确的最小打印次数的(否则本题无解)。因此我们上述的分析可以看做任意两个中间状态转移的“最后一步”,而且不会整体的结果。

对应到本题,题目给定的起始状态是空白字符串 a,目标状态是入参字符串 s。那么真实最优解中,从 a 状态到 s 状态中间可能会经过任意个中间状态,假设有两个中间状态 pq,那么我们上述的分析就可以应用到中间状态 pq 的转移中,可以令得 pq 转移所花费的转移成本最低(最优),同时这个转移不会影响「ap 的转移」和「qs 的转移」,是相互独立的。

因此这个分析可以推广到真实最优转移路径中的任意一步,是一个具有一般性的结论。

上述分析是第一个切入点,第二个切入点是「重复打印会进行覆盖」,这意味着我们其实不需要确保 这一段在目标字符串中完全相同,而只需要 相同即可,即后续打印不会从边缘上覆盖 区间的原有打印,否则 这一段的打印就能用范围更小的区间所代替。

这样就引导出我们状态转移的关键:状态转移之间只需要确保首位字符相同。

动态规划

定义 为将 这一段打印成目标结果所消耗的最小打印次数。

不失一般性考虑 该如何转移:

  • 只染 这个位置,此时
  • 不只染 这个位置,而是从 染到 (需要确保首位相同 ):

其中状态转移方程中的情况 需要说明一下:由于我们只确保 ,并不确保 之间的字符相同,根据我们基本分析可知, 这个点可由打印 的时候一同打印,因此本身 并不独立消耗打印次数,所以这时候 这一段的最小打印次数应该取 ,而不是

最终的 为上述所有方案中取

代码:

class Solution {
    public int strangePrinter(String s) {
        int n = s.length();
        int[][] f = new int[n + 1][n + 1];
        for (int len = 1; len <= n; len++) {
            for (int l = 0; l + len - 1 < n; l++) {
                int r = l + len - 1;
                f[l][r] = f[l + 1][r] + 1;
                for (int k = l + 1; k <= r; k++) {
                    if (s.charAt(l) == s.charAt(k)) {
                        f[l][r] = Math.min(f[l][r], f[l][k - 1] + f[k + 1][r]);
                    }
                }
            }
        }
        return f[0][n - 1];
    }
}
  • 时间复杂度:
  • 空间复杂度:

总结

这道题的原型应该出自 String painter : http://acm.hdu.edu.cn/showproblem.php?pid=2476。

如果只是为了把题做出来,难度不算特别大,根据数据范围 ,可以猜到是 做法,通常就是区间 DP 的「枚举长度 + 枚举左端点 + 枚举分割点」的三重循环。

但是要搞懂为啥可以这样做,还是挺难,大家感兴趣的话可以好好想想 ~ 🤣

最后

这是我们「刷穿 LeetCode」系列文章的第 No.664 篇,系列开始于 2021/01/01,截止于起始日 LeetCode 上共有 1916 道题目,部分是有锁题,我们将先把所有不带锁的题目刷完。

在这个系列文章里面,除了讲解解题思路以外,还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码,我建立了相关的仓库:https://github.com/SharingSource/LogicStack-LeetCode 。

在仓库地址里,你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。

更多更全更热门的「笔试/面试」相关资料可访问排版精美的 合集新基地 🎉🎉

本文由 mdnice 多平台发布文章来源地址https://www.toymoban.com/news/detail-724071.html

到了这里,关于【区间 DP】运用区间 DP 解决古老原题的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 动态规划——区间dp [石子合并]

    动态规划(dp)是一种通过将问题分解为子问题,并利用已解决的子问题的解来求解原问题的方法。适用于具有重叠子问题和最优子结构性质的优化问题。通过定义状态和状态转移方程,动态规划可以在避免重复计算的同时找到问题的最优解,是一种高效的求解方法,常用于

    2024年02月12日
    浏览(46)
  • 动态规划——区间DP 学习笔记

    不含四边形不等式优化。 线性动态规划的局限性在于,它只能顺推或倒退,而不能有子区间依赖的问题。 区间动态规划是线性动态规划的扩展,它将问题划分为若干个子区间,并通过定义状态和状态转移方程来求解每个子区间的最优解,最终得到整个区间的最优解。 区间动

    2024年02月08日
    浏览(42)
  • acwing算法基础之动态规划--线性DP和区间DP

    线性DP:状态转移表达式存在明显的线性关系。 区间DP:与顺序有关,状态与区间有关。 题目1 :数字三角形。 解题思路:直接DP即可, f[i][j] 可以来自 f[i-1][j] + a[i][j] 和 f[i-1][j-1] + a[i][j] ,注意 f[i-1][j] 不存在的情况(最后一个点)和 f[i-1][j-1] 不存在的情况(第一个点)。

    2024年02月04日
    浏览(52)
  • 动态规划系列 | 一文搞定区间DP

    区间 DP 可以用于解决一些涉及到区间合并或分割的问题。区间 DP 通常有以下三个特点: 合并(分割) :将两个或多个部分进行整合,或者反过来将一个区间分解成多个部分。 特征 :能将问题分解为能两两合并的形式。 求解 :对整个问题设最优解,枚举合并点,将问题分

    2024年02月02日
    浏览(47)
  • 蓝桥杯真题:密码脱落(区间dp)

    目录 题目: 解题思路: dp分析:  解题代码: 题目要求的为脱落的种子数(即回文字符中没有对应回文的字符的数量) 我们可以转换成求回文字符串最长回文字符串的长度

    2024年02月16日
    浏览(36)
  • 石子合并(动态规划 区间DP)+详细注释

    原题链接   活动 - AcWing 题目 设有 N 堆石子排成一排,其编号为 1,2,3,…,N。 每堆石子有一定的质量,可以用一个整数来描述,现在要将这 N 堆石子合并成为一堆。 每次只能合并相邻的两堆,合并的代价为这两堆石子的质量之和,合并后与这两堆石子相邻的石子将和新堆相

    2024年02月16日
    浏览(39)
  • 算法基础复盘笔记Day11【动态规划】—— 区间DP、计数类DP、树形DP、记忆化搜索

    ❤ 作者主页:欢迎来到我的技术博客😎 ❀ 个人介绍:大家好,本人热衷于 Java后端开发 ,欢迎来交流学习哦!( ̄▽ ̄)~* 🍊 如果文章对您有帮助,记得 关注 、 点赞 、 收藏 、 评论 ⭐️⭐️⭐️ 📣 您的支持将是我创作的动力,让我们一起加油进步吧!!!🎉🎉 1. 题目

    2024年02月01日
    浏览(42)
  • AcWing算法学习笔记:动态规划(背包 + 线性dp + 区间dp + 计数dp + 状态压缩dp + 树形dp + 记忆化搜索)

    算法 复杂度 时间复杂度0(nm) 空间复杂度0(nv) 代码 算法 通过滚动数组对01背包朴素版进行空间上的优化 f[i] 与 f[i - 1]轮流交替 若体积从小到大进行遍历,当更新f[i, j]时,f[i - 1, j - vi] 已经在更新f[i, j - vi]时被更新了 因此体积需要从大到小进行遍历,当更新f[i, j]时,f[i - 1,

    2024年02月21日
    浏览(43)
  • 【动态规划】LeetCode 312. 戳气球 --区间DP问题

      Halo,这里是Ppeua。平时主要更新C语言,C++,数据结构算法......感兴趣就关注我吧!你定不会失望。 🌈个人主页:主页链接 🌈算法专栏:专栏链接       我会一直往里填充内容哒! 🌈LeetCode专栏:专栏链接       目前在刷初级算法的LeetBook 。若每日一题当中有力所能

    2023年04月16日
    浏览(39)
  • day78【代码随想录】区间DP专题

    1、多边形三角剖分的最低得分 2、猜数字大小 II 3、让字符串成为回文串的最少插入次数 4、切棍子的最小成本 5、戳气球 6、合并石头的最低成本 分析: 大佬详细题解 分析: 这一段题解是灵魂! 大佬题解 类似于算法书中的矩阵连乘问题 分析: 跟判断回文串思路一样,但是

    2023年04月13日
    浏览(74)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包