0664. 奇怪的打印机

题目地址(664. 奇怪的打印机)

https://leetcode-cn.com/problems/strange-printer/

题目描述

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

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

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

 

示例 1：

输入：s = "aaabbb"
输出：2
解释：首先打印 "aaa" 然后打印 "bbb"。


示例 2：

输入：s = "aba"
输出：2
解释：首先打印 "aaa" 然后在第二个位置打印 "b" 覆盖掉原来的字符 'a'。


 

提示：

1 <= s.length <= 100
s 由小写英文字母组成

前置知识

• 动态规划

• 区间 DP

公司

• 暂无

思路

西法在动态规划专栏 中提到了区间 DP。

原文部分内容如下：

---

区间类动态规划是线性动态规划的扩展，它在分阶段地划分问题时，与阶段中元素出现的顺序和由前一阶段的哪些元素合并而来有很大的关系。令状态 $f(i,j)$ 表示将下标位置 $i$ 到 $j$ 的所有元素合并能获得的价值的最大值，那么 $f(i,j)=\max{f(i,k)+f(k+1,j)+cost}$，$cost$ 为将这两组元素合并起来的代价。

区间 DP 的特点：

合并：即将两个或多个部分进行整合，当然也可以反过来；

特征：能将问题分解为能两两合并的形式；

求解：对整个问题设最优值，枚举合并点，将问题分解为左右两个部分，最后合并两个部分的最优值得到原问题的最优值。

---

之所以称其为动态规划问题的扩展是因为：很多 DP 问题可以看成是区间为 [0, end] 或者 [start, n] 的区间 DP，也就是说是一端固定的区间 DP。 因此枚举所有区间不需要平方的复杂度，而是仅仅需要线性的时间。对应这道题来说，如果题目改为：

• 每次可以在任意起始位置到最后的位置打印新字符

• 或者改为每次可以在初始位置到任意位置打印新字符

那么问题降级为普通的 DP。大家可以试一下如何解决。

回到这道题。正如前面所描述的那样，这道题每次可以在任意起始和结束位置打印新字符。 因此我们需要暴力枚举所有的起始位置和结束位置的笛卡尔积。

具体来说，我们可以首先将区间分为 A 和 B 两部分。接下来，递归地执行分割与打印工作，并取最小值即可。

如何划分为 A 和 B 呢？暴力枚举分割点即可，不难知道分割点属于区间 [l,r-1]， 这样 A 部分就是 s[:l+1], B 部分就是 s[l+1:r+1]。那么分别解决 A 和 B ，之后将其合并即可。而合并的代价是 0。直接套用上面的公式即可。

$f(i,j)=\max{f(i,k)+f(k+1,j)+cost}$

答案就是$ f(0, n - 1)$,其中 n 为字符串 s 的长度。

核心代码：

def dp(l, r):
    # ...
    # 将 分别处理 A 和 部分
    for i in range(l, r):
        ans = min(ans, dp(l, i) + dp(i + 1, r))
    # ...
dp(0, len(s) - 1)

实际上上面的代码意思是：对于一次打印，必不会贯穿 A 和 B，也就是说至少要打印两次，一次是 A 部分的打印，一次是 B 部分的打印。之所以说至少是因为我们可能继续递归打印。

而对于 aaaaaa 这样的情况，很明显只需要打印一次，没有必要枚举分割点。

如何处理这种情况呢？实际上我们可以考虑从 l （左端点）位置开始打印，而结束的具体位置不确定，但可以确定的是增加 r 不会对结果有影响，也就是说 f(l, r-1) 等价于 f(l, r)。说人话就是从 l （左端点）开始打印的时候总可以顺便把 r 给打印了。这个算法可以扩展到任意 s[l] == s[r] 的情况，而不仅仅是上面的字符全部相等的情况。

代码:

def dp(l, r):
    # ...
    if s[l] == s[r]:
        return dp(l, r - 1)
    # ...

关键点

代码

• 语言支持：Python3

Python3 Code:

class Solution:
    def strangePrinter(self, s: str) -> int:
        @lru_cache(None)
        def dp(l, r):
            if l >= r:
                return int(l == r)
            if s[l] == s[r]:
                return dp(l, r - 1)
            ans = len(s)
            #  枚举分割点
            for i in range(l, r):
                ans = min(ans, dp(l, i) + dp(i + 1, r))
            return ans

        return dp(0, len(s) - 1)

复杂度分析

令 n 为数组长度。

• 时间复杂度：枚举状态的时间为 $O(n^2)$，递归函数内部的时间为 $O(n)$，总共就是 $O(n^3)$

• 空间复杂度：空间复杂度取决于状态总数，而状态总数为 $O(n^2)$，因此空间复杂度为 $O(n^2)$

此题解由 力扣刷题插件 自动生成。

力扣的小伙伴可以关注我，这样就会第一时间收到我的动态啦~

以上就是本文的全部内容了。大家对此有何看法，欢迎给我留言，我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库：https://github.com/azl397985856/leetcode 。 目前已经 40K star 啦。大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。

关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。