常州网站排名优化,wordpress门户,秘密入口3秒自动进入,有哪些做ppt网站文章目录1. 题目2. 解题1. 题目
有台奇怪的打印机有以下两个特殊要求#xff1a;
打印机每次只能打印由 同一个字符 组成的序列。每次可以在任意起始和结束位置打印新字符#xff0c;并且会覆盖掉原来已有的字符。
给你一个字符串 s #xff0c;你的任务是计算这个打印机…
文章目录1. 题目2. 解题1. 题目
有台奇怪的打印机有以下两个特殊要求
打印机每次只能打印由 同一个字符 组成的序列。每次可以在任意起始和结束位置打印新字符并且会覆盖掉原来已有的字符。
给你一个字符串 s 你的任务是计算这个打印机打印它需要的最少打印次数。
示例 1
输入s aaabbb
输出2
解释首先打印 aaa 然后打印 bbb。示例 2
输入s aba
输出2
解释首先打印 aaa 然后在第二个位置打印 b 覆盖掉原来的字符 a。提示
1 s.length 100
s 由小写英文字母组成来源力扣LeetCode 链接https://leetcode-cn.com/problems/strange-printer 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。 2. 解题
dp[i][j] 表示打印 区间 [i,j] 需要的最少次数
class Solution {
public:int strangePrinter(string s) {int n s.size();vectorvectorint dp(n, vectorint(n, INT_MAX));for(int i 0; i n; i)dp[i][i] 1; // 初始情况for(int j 1; j n; j){for(int i j-1; i 0; --i){if(s[i] s[j]) // 两端的字符一样dp[i][j] dp[i][j-1]; // j 字符 可以 跟 i 一同打印else // 两端不一样枚举区间的中间切分点{for(int k i; k j; k){dp[i][j] min(dp[i][j], dp[i][k]dp[k1][j]);}}}}return dp[0][n-1];}
};144 ms 9.2 MB C 我的CSDN博客地址 https://michael.blog.csdn.net/
长按或扫码关注我的公众号Michael阿明一起加油、一起学习进步
