664 奇怪的打印机（区间dp）

妖狐艹你老母 2022-09-02 08:08 159阅读 0赞

**1. 问题描述：**

有台奇怪的打印机有以下两个特殊要求：  
打印机每次只能打印由同一个字符组成的序列。  
每次可以在任意起始和结束位置打印新字符，并且会覆盖掉原来已有的字符。  
给你一个字符串 s ，你的任务是计算这个打印机打印它需要的最少打印次数。

**示例 1：**

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

**示例 2：**

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

**提示：**

1 <= s.length <= 100  
s 由小写英文字母组成  
来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/strange-printer

**2. 思路分析：**

这道题目属于dp的题目，思路比较难想。对于**动态规划**的题目主要有两个步骤：① 状态表示 ② 状态计算；状态表示比较好想，因为是需要打印出当前s的所有字符，所以我们可以定义一个二维dp数组，其中dp\[i\]\[j\]表示打印出区间\[i:j\]的所有字符的最少操作次数（区间dp的定义方式），这道题目的核心在于状态计算。我们采取的策略是先打印出最开始的第一个字符（特殊情况），这个时候dp\[i\]\[j\] = 1 + dp\[i + 1\]\[j\]，然后我们计算枚举区间\[i + 1:j\]的所有状态的集合，并且只有当s\[i\] == s\[j\]的时候才枚举区间\[i + 1:j\]的所有状态，所以当s\[i\] == s\[k\]的时候我们可以枚举以k为终点的所有的s\[k\] = s\[i\]的前缀，位置k后面的状态其实很好求解为dp\[k + 1\]\[j\]，所以关键是前半部分的状态计算，前面的状态是从最开始的位置i开始刷一直到某一个位置，从某一个位置开始到k的位置都会被覆盖为其他的字符，所以我们不妨可以从i刷到k - 1这个位置，即使从某个位置开始的区间被覆盖了也没有关系因为延长刷的长度不会影响当前操作的次数，所以枚举\[i+1:j\]的状态转移方程为dp\[i\]\[j\] = min(dp\[i\]\[j\], dp\[i + 1\]\[k - 1\] + dp\[k + 1\]\[j\])。

**3. 代码如下：**

class Solution:
        # 区间dp
        def strangePrinter(self, s: str) -> int:
            n = len(s)
            if n == 0: return 0
            dp = [[0] * (n + 1) for i in range(n + 1)]
            for l in range(1, n + 1):
                i = 0
                while i + l - 1 < n:
                    j = i + l - 1
                    dp[i][j] = 1 + dp[i + 1][j]
                    for k in range(i + 1, j + 1):
                        if s[i] == s[k]:
                            dp[i][j] = min(dp[i][j], dp[i][k - 1] + dp[k + 1][j])
                    i += 1
            return dp[0][n - 1]