前端刷题路-Day49：奇怪的打印机（题号664）

这是我参与更文挑战的第13天，活动详情查看： 更文挑战

奇怪的打印机（题号664）

题目

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

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

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

示例 1：

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

示例 2：

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

提示：

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

链接

leetcode-cn.com/problems/st…

解释

这题啊，这题是经典动态规划。

题目中表示的最少打印次数，就是求最优解，很明显需要用到动态规划。

一开始笔者其实走进了一个误区，总想着考虑各种情况，因为其实很明显，如果首尾的字母相同，那么就可以减少一次打印次数。同时如果当前字母和前一个字母相同，也可以减少一次打印次数。

笔者尝试找到字母的组合情况，然后根据情况来进行不同的计数方式，在尝试了3次后决定放弃，显然这是一种不可能完成的工作。

那么应该怎么做呢？笔者思考后毫无头绪，最后只能看了答案，原来还是DP的思路错了。

这题应该考虑的是区间，而不是各种情况。

这里可以把字符串拆成一个个区间，比方说这样的一个?：

'abbbc'
复制代码

首先将这里栗子拆分成两个区间：

'abb', 'bc'
复制代码

然后再拆，一直拆下去会变成?：

'a', 'b', 'b', 'b', 'c'
复制代码

每个单独区间的打印次数都是一次，那么就可以拿这个作为基准，开始一点点扩大区间。

先看ab区间，显然是需要打印两次的，之后看bb区间，打印一次，找到所有的两个字母的区间，结果应该是：

'ab': 2
'bb': 1
'bb': 1
'bc': 2
复制代码

找到这些区间后即可扩大区间，变成3个字母，4个字母和最后5个字母的区间。

具体的区间方法会放到答案里面进行详细解释，这里仅仅提供下思路。

自己的答案

无

更好的方法（DP）

老规矩，先看代码?：

var strangePrinter = function(s) {
  var len = s.length
      dp = Array.from({length: len}, () => new Array(len).fill(0))
  for (let i = len - 1; i >= 0; i--) {
    dp[i][i] = 1
    for (let j = i + 1; j < len; j++) {
      if (s[i] === s[j]) {
        dp[i][j] = dp[i][j - 1]
      } else {
        var min = Number.MAX_SAFE_INTEGER
        for (let k = i; k < j; k++) {
          min = Math.min(min, dp[i][k] + dp[k+1][j])          
        }
        dp[i][j] = min
      }
    }
  }
  return dp[0][len - 1]
}
复制代码

先看DP的定义，是一个二维数组，这个二位数组代表着什么呢？

DP[i][j]其实代表着字符串从i开始到j结尾这个区间内到最小打印次数。

那借用解释里的一种情况，如果这个区间只有一个值，该区间的最小打印次数为1，也就是说DP[i][i] = 1。

DP数组初始化完成后开始循环，这里借用官方解释的原话：

为了保证动态规划的计算过程满足无后效性，在实际代码中，我们需要改变动态规划的计算顺序，从大到小地枚举 i

具体的原因笔者也只能GET到一部分，可以这样设想一下，如果是从前往后，那么后面的数据可能会出现不准的情况，笔者也仅仅是有这种感觉，具体原因也说不太清楚，尽力局。

首先第一层循环，从后往前，i从大到小。在i循环内部要做的第一件事就是初始值的赋值：

dp[i][i] = 1
复制代码

也就是区间长度为1时打印次数为1。

然后开始内层循环，此时就可以从前往后了，也就是i到数组末尾的区间。

如果区间首尾相同，也就是s[i] === s[j]，那么直接取少一个字母的区间值即可，因为可以节省一次打印，这一部分比较简单。

然后就是内部的k循环了，也是最后一层循环。

这一层的循环就是拼接i到j区间内的所有小区间，从代码可以看出来，拼接的过程其实就是取最小值，比方说这样的一个小区间：

'abcd'
复制代码

那比较的元素就是：

'a', 'bcd'
'ab', 'cd'
'abc', 'd'
'abcd'
复制代码

取这些组合里的最小值既是这个区间内的最小打印次数，以此类推，即可即可扩展区间到整个字符串的区间，拿到最后的结果。

这题就这样了，确实比扰绕，相对来说比较复杂，三层循环较难想到。

时间复杂度是O(n^3)，其中 n 是字符串的长度。

空间复杂度时O(n^2)，其中 n 是字符串的长度。需要保存所有 n^2 个状态。

PS：想查看往期文章和题目可以点击下面的链接：

这里是按照日期分类的?

前端刷题路-目录（日期分类）

经过有些朋友的提醒，感觉也应该按照题型分类
这里是按照题型分类的?

前端刷题路-目录（题型分类）

有兴趣的也可以看看我的个人主页?

Here is RZ