0664-奇怪的打印机

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:06:25 2023-09-13 16:06:25 Updated    

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

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

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

示例 1：

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

示例 2：

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

提示：

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

方法一：动态规划

思路及算法

我们可以使用动态规划解决本题，令 f[i][j] 表示打印完成区间 [i,j] 的最少操作数。

当我们尝试计算出 f[i][j] 时，需要考虑两种情况：

  1. s[i]=s[j]，即区间两端的字符相同，那么当我们打印左侧字符 s[i] 时，可以顺便打印右侧字符 s[j]，这样我们即可忽略右侧字符对该区间的影响，只需要考虑如何尽快打印完区间 [i,j-1] 即可，即此时有 f[i][j]=f[i][j-1]。
    • 我们无需关心区间 [i,j-1] 的具体打印方案，因为我们总可以第一步完成 s[i] 的打印，此时可以顺便完成 s[j] 的打印，不会影响打印完成区间 [i,j-1] 的最少操作数。
  2. s[i] \neq s[j]，即区间两端的字符不同，那么我们需要分别完成该区间的左右两部分的打印。我们记两部分分别为区间 [i,k] 和区间 [k+1,j]（其中 i \leq k < j），此时 f[i][j]=\min_{k=i}^{j-1}{f[i][k]+f[k+1][j]。

总结状态转移方程为：

f[i][j] =
\begin{cases}
f[i][j-1],& s[i]=s[j] \
\min_{k=i}^{j-1}{f[i][k]+f[k+1][j]},& s[i]\neq s[j]
\end{cases}

边界条件为 f[i][i]=1，对于长度为 1 的区间，需要打印 1 次。最后的答案为 f[0][n-1]。

注意到 f[i][j] 的计算需要用到 f[i][k] 和 f[k+1][j]（其中 i\leq k< j）。为了保证动态规划的计算过程满足无后效性，在实际代码中，我们需要改变动态规划的计算顺序，从大到小地枚举 i，并从小到大地枚举 j，这样可以保证当计算 f[i][j] 时，f[i][k] 和 f[k+1][j] 都已经被计算过。

代码

[sol1-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    int strangePrinter(string s) {
        int n = s.length();
        vector<vector<int>> f(n, vector<int>(n));
        for (int i = n - 1; i >= 0; i--) {
            f[i][i] = 1;
            for (int j = i + 1; j < n; j++) {
                if (s[i] == s[j]) {
                    f[i][j] = f[i][j - 1];
                } else {
                    int minn = INT_MAX;
                    for (int k = i; k < j; k++) {
                        minn = min(minn, f[i][k] + f[k + 1][j]);
                    }
                    f[i][j] = minn;
                }
            }
        }
        return f[0][n - 1];
    }
};
[sol1-Java]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int strangePrinter(String s) {
        int n = s.length();
        int[][] f = new int[n][n];
        for (int i = n - 1; i >= 0; i--) {
            f[i][i] = 1;
            for (int j = i + 1; j < n; j++) {
                if (s.charAt(i) == s.charAt(j)) {
                    f[i][j] = f[i][j - 1];
                } else {
                    int minn = Integer.MAX_VALUE;
                    for (int k = i; k < j; k++) {
                        minn = Math.min(minn, f[i][k] + f[k + 1][j]);
                    }
                    f[i][j] = minn;
                }
            }
        }
        return f[0][n - 1];
    }
}
[sol1-C#]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public class Solution {
    public int StrangePrinter(string s) {
        int n = s.Length;
        int[,] f = new int[n, n];
        for (int i = n - 1; i >= 0; i--) {
            f[i, i] = 1;
            for (int j = i + 1; j < n; j++) {
                if (s[i] == s[j]) {
                    f[i, j] = f[i, j - 1];
                } else {
                    int minn = int.MaxValue;
                    for (int k = i; k < j; k++) {
                        minn = Math.Min(minn, f[i, k] + f[k + 1, j]);
                    }
                    f[i, j] = minn;
                }
            }
        }
        return f[0, n - 1];
    }
}
[sol1-JavaScript]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
var strangePrinter = function(s) {
    const n = s.length;
    const f = new Array(n).fill(0).map(() => new Array(n).fill(0));
    for (let i = n - 1; i >= 0; i--) {
        f[i][i] = 1;
        for (let j = i + 1; j < n; j++) {
            if (s[i] == s[j]) {
                f[i][j] = f[i][j - 1];
            } else {
                let minn = Number.MAX_SAFE_INTEGER;
                for (let k = i; k < j; k++) {
                    minn = Math.min(minn, f[i][k] + f[k + 1][j]);
                }
                f[i][j] = minn;
            }
        }
    }
    return f[0][n - 1];
};
[sol1-Golang]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
func strangePrinter(s string) int {
    n := len(s)
    f := make([][]int, n)
    for i := range f {
        f[i] = make([]int, n)
    }
    for i := n - 1; i >= 0; i-- {
        f[i][i] = 1
        for j := i + 1; j < n; j++ {
            if s[i] == s[j] {
                f[i][j] = f[i][j-1]
            } else {
                f[i][j] = math.MaxInt64
                for k := i; k < j; k++ {
                    f[i][j] = min(f[i][j], f[i][k]+f[k+1][j])
                }
            }
        }
    }
    return f[0][n-1]
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}
[sol1-C]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int strangePrinter(char* s) {
    int n = strlen(s);
    int f[n][n];
    for (int i = n - 1; i >= 0; i--) {
        f[i][i] = 1;
        for (int j = i + 1; j < n; j++) {
            if (s[i] == s[j]) {
                f[i][j] = f[i][j - 1];
            } else {
                int minn = INT_MAX;
                for (int k = i; k < j; k++) {
                    minn = fmin(minn, f[i][k] + f[k + 1][j]);
                }
                f[i][j] = minn;
            }
        }
    }
    return f[0][n - 1];

复杂度分析

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

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

 Comments
On this page
0664-奇怪的打印机