上海企业网站开发,网站前台如何刷新,江苏建设工程有限公司简介,平台网站建设哪家好题目链接 Leetcode.664 奇怪的打印机 hard 题目描述
有台奇怪的打印机有以下两个特殊要求#xff1a;
打印机每次只能打印由 同一个字符 组成的序列。每次可以在从起始到结束的任意位置打印新字符#xff0c;并且会覆盖掉原来已有的字符。
给你一个字符串 s #xff0c;你…题目链接 Leetcode.664 奇怪的打印机 hard 题目描述
有台奇怪的打印机有以下两个特殊要求
打印机每次只能打印由 同一个字符 组成的序列。每次可以在从起始到结束的任意位置打印新字符并且会覆盖掉原来已有的字符。
给你一个字符串 s 你的任务是计算这个打印机打印它需要的最少打印次数。
示例 1 输入s “aaabbb” 输出2 解释首先打印 “aaa” 然后打印 “bbb”。 示例 2 输入s “aba” 输出2 解释首先打印 “aaa” 然后在第二个位置打印 “b” 覆盖掉原来的字符 ‘a’。 提示 1 ≤ s . l e n g t h ≤ 100 1 \leq s.length \leq 100 1≤s.length≤100s 由小写英文字母组成
解法区间dp
s a需要打印 1 1 1 次s ab需要打印 2 2 2 次s aba需要打印 2 2 2 次s abab需要打印 3 3 3 次
当 最后一个字符 和 第一个字符 相同 时例如 s aba 。那么 s aba 就和 s ab的打印次数一样。
当 最后一个字符 和 第一个字符 不同 时例如 s abab。那么 s abab 的打印次数就应该是所有组合中最小的打印次数
a bab 1 2 3ab ab 2 2 4aba b 2 1 3
所以 s abab 的最少打印次数是 3 3 3。
我们定义 f ( i , j ) f(i,j) f(i,j) 为打印区间 [ i , j ] [i,j] [i,j] 所需要的最少打印次数那么最终返回的答案就是 f ( 0 , n − 1 ) f(0,n-1) f(0,n−1)。
当 i j i j ij时区间 [ i , j ] [i,j] [i,j] 只有一个字符所以只需要打印一次即 f ( i , j ) 1 f(i,j) 1 f(i,j)1当 s [ i ] s [ j ] s[i] s[j] s[i]s[j]时 f ( i , j ) f ( i , j − 1 ) f(i,j) f(i,j-1) f(i,j)f(i,j−1)当 s [ i ] ≠ s [ j ] s[i] \neq s[j] s[i]s[j]时 f ( i , j ) m i n { f ( i , k ) f ( k 1 , j ) } ( i ≤ k j ) f(i,j) min\{ f(i,k) f(k1,j) \} \quad (i \leq k j) f(i,j)min{f(i,k)f(k1,j)}(i≤kj)
时间复杂度 O ( n 3 ) O(n^3) O(n3)
C代码
class Solution {
public:int strangePrinter(string s) {int n s.size();vectorvectorint f(n,vectorint(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[k1][j]);}//printf(f[%d][%d] %d\n,i,j,f[i][j]);}}return f[0][n-1];}
};
