中国建设住建网站,网络推广培训班4800块钱贵吗,免费个人搭建网站,海南省住建设厅网站报监的工程题目描述 这是 LeetCode 上的 「664. 奇怪的打印机」 #xff0c;难度为 「困难」。 Tag : 「区间 DP」 有台奇怪的打印机有以下两个特殊要求#xff1a; 打印机每次只能打印由 同一个字符 组成的序列。 每次可以在任意起始和结束位置打印新字符#xff0c;并且会覆盖掉原来… 题目描述 这是 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 必然是可以「归到同一次打印」中。 我们可以不失一般性证明「连续相同的一段字符必然可以归到同一次打印中而不会让打印次数变多」这个推理是否正确 假设有目标序列 其中 连续一段字符相同假如这一段的打印被最后完成注意最后完成不代表这一段要保留空白这一段可以此前被打印多次除了这一段以外所消耗的打印次数为 那么根据 不同的打印方案有 将 单纯划分为多段总共打印的次数大于 此方案不会取到打印最小值 可忽略 将 归到同一次打印总共打印的次数等于 将 结合之前的打印划分为多段即 一段的两段本身就是「目标字符」我们本次只需要打印 中间的部分。总共打印的次数等于 由于同样的地方可以被重复打印因此我们可以将情况 中打印边缘扩展到 和 处这样最终打印结果不变而且总的打印次数没有增加。 到这一步我们其实已经证明出「连续相同的一段字符必然可以归到同一次打印中而不会让打印次数变多」的推论成立了。 但可能会有同学提出疑问怎么保证 是被最后涂的怎么保证 不是和其他「不相邻的同样字符」一起打印的 答案是不用保证因为不同状态打印结果之间相互独立而有明确的最小转移成本。即从当前打印结果 a 变成打印结果 b是具有明确的最小打印次数的否则本题无解。因此我们上述的分析可以看做任意两个中间状态转移的“最后一步”而且不会整体的结果。 对应到本题题目给定的起始状态是空白字符串 a目标状态是入参字符串 s。那么真实最优解中从 a 状态到 s 状态中间可能会经过任意个中间状态假设有两个中间状态 p 和 q那么我们上述的分析就可以应用到中间状态 p 到 q 的转移中可以令得 p 到 q 转移所花费的转移成本最低最优同时这个转移不会影响「a 到 p 的转移」和「q 到 s 的转移」是相互独立的。 因此这个分析可以推广到真实最优转移路径中的任意一步是一个具有一般性的结论。 上述分析是第一个切入点第二个切入点是「重复打印会进行覆盖」这意味着我们其实不需要确保 这一段在目标字符串中完全相同而只需要 相同即可即后续打印不会从边缘上覆盖 区间的原有打印否则 这一段的打印就能用范围更小的区间所代替。 这样就引导出我们状态转移的关键状态转移之间只需要确保首位字符相同。 动态规划 定义 为将 这一段打印成目标结果所消耗的最小打印次数。 不失一般性考虑 该如何转移 只染 这个位置此时 不只染 这个位置而是从 染到 需要确保首位相同 其中状态转移方程中的情况 需要说明一下由于我们只确保 并不确保 之间的字符相同根据我们基本分析可知 这个点可由打印 的时候一同打印因此本身 并不独立消耗打印次数所以这时候 这一段的最小打印次数应该取 而不是 。 最终的 为上述所有方案中取 。 代码 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?pid2476。 如果只是为了把题做出来难度不算特别大根据数据范围 可以猜到是 做法通常就是区间 DP 的「枚举长度 枚举左端点 枚举分割点」的三重循环。 但是要搞懂为啥可以这样做还是挺难大家感兴趣的话可以好好想想 ~ 最后 这是我们「刷穿 LeetCode」系列文章的第 No.664 篇系列开始于 2021/01/01截止于起始日 LeetCode 上共有 1916 道题目部分是有锁题我们将先把所有不带锁的题目刷完。 在这个系列文章里面除了讲解解题思路以外还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。 为了方便各位同学能够电脑上进行调试和提交代码我建立了相关的仓库https://github.com/SharingSource/LogicStack-LeetCode 。 在仓库地址里你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。 更多更全更热门的「笔试/面试」相关资料可访问排版精美的 合集新基地 本文由 mdnice 多平台发布
