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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
|
// 664. Strange Printer
#include "leetcode.h"
/*
* there is a strange printer with the following two special properties:
* - the printer can only print a sequence of the same character each time
* - at each turn, the printer can print new characters starting from and eding
* at any place and will cover the origin existing characters given a string
* 's', return the minimum number of turns the printer needed to print it.
*/
int get_cnt(char *s, int **dp, int r, int l) {
if (dp[r][l] != -1)
return dp[r][l];
else {
int i = r;
while (i < l && s[i] == s[l])
i++;
int min = l - i;
for (int j = i; j < l; j++)
if (get_cnt(s, dp, i, j) + get_cnt(s, dp, j + 1, l) + 1 < min)
min = get_cnt(s, dp, i, j) + get_cnt(s, dp, j + 1, l) + 1;
dp[r][l] = min;
return dp[r][l];
}
}
int strangePrinter(char *s) {
int n = strlen(s);
int **dp = (int **)malloc(n * sizeof(int *));
for (int i = 0; i < n; i++) {
dp[i] = (int *)malloc(n * sizeof(int));
dp[i][i] = 0;
for (int j = i + 1; j < n; j++)
dp[i][j] = -1;
}
return get_cnt(s, dp, 0, n - 1) + 1;
}
int main() {
char s1[] = {"aaabbb"}, s2[] = {"aba"};
printf("%d\n", strangePrinter(s1)); // expect: 2
printf("%d\n", strangePrinter(s2)); // expect: 2
}
|