题目描述
这是 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?pid=2476。
如果只是为了把题做出来,难度不算特别大,根据数据范围 ,可以猜到是 做法,通常就是区间 DP 的「枚举长度 + 枚举左端点 + 枚举分割点」的三重循环。
但是要搞懂为啥可以这样做,还是挺难,大家感兴趣的话可以好好想想 ~ 🤣
最后
这是我们「刷穿 LeetCode」系列文章的第 No.664
篇,系列开始于 2021/01/01,截止于起始日 LeetCode 上共有 1916 道题目,部分是有锁题,我们将先把所有不带锁的题目刷完。
在这个系列文章里面,除了讲解解题思路以外,还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码,我建立了相关的仓库:https://github.com/SharingSource/LogicStack-LeetCode 。
在仓库地址里,你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。
更多更全更热门的「笔试/面试」相关资料可访问排版精美的 合集新基地 🎉🎉文章来源:https://www.toymoban.com/news/detail-724071.html
本文由 mdnice 多平台发布文章来源地址https://www.toymoban.com/news/detail-724071.html
到了这里,关于【区间 DP】运用区间 DP 解决古老原题的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!