【Day28】664.奇怪的打印机

664. 奇怪的打印机

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

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

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

示例 1:

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

示例 2:

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

提示:

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

题解:

区间dp问题,对于[i,j]区间i<j,如果s[i] == s[j],那么dp[i][j] = dp[i - 1][j] 或者dp[i + 1][j],例如:aba 等于 ab或者 ba

如果s[i]!=s[j],那么对于区间[i,j]的所有组合,进行累加求min即可。

dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j])

目标是求dp[0][n - 1],因此,对于这道题有两种遍历方式。

第一种:从下往上,从左到右。

class Solution {
public:
    int strangePrinter(string s) {
        // aba
        // aaabbb
        int n = s.size();
        int dp[n][n];
        memset(dp, 0x3f3f3f3f, sizeof(dp));
        for (int i = 0; i < n; i++) {
            dp[i][i] = 1;
        }

        for (int i = n - 1; i >= 0; i--) {
            for (int j = i + 1; j < n; j++) {
                if (s[i] == s[j]) {
                    dp[i][j] = dp[i][j - 1];
                } else {
                    for (int k = i; k < j; k++) {
                        dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j]);
                    }
                }
            }
        }     
        return dp[0][n - 1];
    }
};

第二种:斜着遍历。

class Solution {
public:
    int strangePrinter(string s) {
        // aba
        // aaabbb
        int n = s.size();
        int dp[n][n];
        memset(dp, 0x3f3f3f3f, sizeof(dp));
        for (int i = 0; i < n; i++) {
            dp[i][i] = 1;
        }

        for (int l = 2; l <= n; l++) {
            for (int i = 0; i < n - l + 1; i++) {
                int j = l + i - 1;
                if (s[i] == s[j]) {
                    dp[i][j] = dp[i][j - 1];
                } else {
                    for (int k = i; k < j; k++) {
                        dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j]);
                    }
                }
            }
        }


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

   转载规则


《【Day28】664.奇怪的打印机》 Tyzhao 采用 知识共享署名 4.0 国际许可协议 进行许可。
 上一篇
【Day29】1787.使所有区间的异或结果为零 【Day29】1787.使所有区间的异或结果为零
1787. 使所有区间的异或结果为零给你一个整数数组 nums 和一个整数 k 。区间 [left, right](left <= right)的 异或结果 是对下标位于 left 和 right(包括 left 和 right )之
2021-05-25
下一篇 
【Day27】1707.与数组中元素的最大异或值 【Day27】1707.与数组中元素的最大异或值
1707. 与数组中元素的最大异或值给你一个由非负整数组成的数组 nums 。另有一个查询数组 queries ,其中 queries[i] = [xi, mi] 。 第 i 个查询的答案是 xi 和任何 nums 数组中不超过 mi 的元
2021-05-23
  目录