Leetcode.664 奇怪的打印机-Toy模板网

这篇具有很好参考价值的文章主要介绍了Leetcode.664 奇怪的打印机。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

题目链接

Leetcode.664 奇怪的打印机 hard

题目描述

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

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

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

示例 1：

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

示例 2：

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

提示：

$\leq s.length \leq 100$
s 由小写英文字母组成

解法：区间dp

s = "a"，需要打印 $1$ 次；
s = "ab"，需要打印 $2$ 次；
s = "aba"，需要打印 $2$ 次；
s = "abab"，需要打印 $3$ 次；

当最后一个字符和第一个字符相同时，例如 s = "aba" 。那么 s = "aba" 就和 s = "ab"的打印次数一样。

当最后一个字符和第一个字符不同时，例如 s = "abab"。那么 s = "abab" 的打印次数，就应该是所有组合中最小的打印次数：

a + bab = 1 + 2 = 3；
ab + ab = 2 + 2 = 4；
aba + b = 2 + 1 = 3；

所以 s = "abab" 的最少打印次数是 $3$ 。

我们定义 $f (i, j)$ 为打印区间 $[i, j]$ 所需要的最少打印次数，那么最终返回的答案就是 $f (0, n - 1)$ 。

当 $i = j$ 时，区间 $[i, j]$ 只有一个字符，所以只需要打印一次，即 $f (i, j) = 1$ ；
当 $s [i] = s [j]$ 时， $f (i, j) = f (i, j - 1)$ ；
当 $\neq s[j]$ 时， $min\{ f(i,k) + f(k+1,j) \} \quad (i \leq k < j)$ ；

时间复杂度： $O(n^3)$

C++代码：文章来源地址https://www.toymoban.com/news/detail-708382.html

class Solution {
public:
    int strangePrinter(string s) {
        int n = s.size();
        vector<vector<int>> f(n,vector<int>(n,1e9));

        for(int i = 0;i < n;i++) f[i][i] = 1;

        for(int i = n-1;i >= 0;i--){
            for(int j = i + 1;j < n;j++){
                if(s[i] == s[j]){
                     f[i][j] = f[i][j - 1];
                }
                else{
                    for(int k = i;k < j;k++) f[i][j] = min(f[i][j] , f[i][k]+f[k+1][j]);
                }
                    //printf("f[%d][%d] = %d\n",i,j,f[i][j]);
            }
        }

        return f[0][n-1];
    }
};