大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。
Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺
有台奇怪的打印机有以下两个特殊要求:
打印机每次只能打印由 同一个字符 组成的序列。
每次可以在任意起始和结束位置打印新字符,并且会覆盖掉原来已有的字符。
给你一个字符串 s ,你的任务是计算这个打印机打印它需要的最少打印次数。
示例 1:
输入:s = "aaabbb"
输出:2
解释:首先打印 "aaa" 然后打印 "bbb"。
示例 2:
输入:s = "aba"
输出:2
解释:首先打印 "aaa" 然后在第二个位置打印 "b" 覆盖掉原来的字符 'a'。
提示:
1 <= s.length <= 100
s 由小写英文字母组成
const int N = 1e3 + 10;
const int INF = 0x3f3f3f3f;
int f[N][N] = {
0};
class Solution {
public:
int strangePrinter(string s) {
int n = s.size();
memset(f,0x3f,sizeof f);
for(int len = 1;len <= n;len ++){
for(int l = 0;l <= n - len;l ++){
int r = l + len - 1;
if(l == r)f[l][r] = 1;
else{
if(s[l] == s[r])f[l][r] = f[l][r - 1];
else{
for(int k = l;k < r;k ++){
f[l][r] = min(f[l][r],f[l][k] + f[k + 1][r]);
}
}
}
}
}
return f[0][n - 1];
}
};
发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/169068.html原文链接:https://javaforall.cn
【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛
【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...