leetcode664. 奇怪的打印机【DP】

痛定思痛。 2022-10-15 10:54 88阅读 0赞

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

打印机每次只能打印由 同一个字符 组成的序列。  
每次可以在任意起始和结束位置打印新字符，并且会覆盖掉原来已有的字符。  
给你一个字符串 s ，你的任务是计算这个打印机打印它需要的最少打印次数。

示例 1：

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

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

提示：

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

class Solution {
    public:
        int strangePrinter(string s) {
            int d[100][100];
            int n= s.length();
            for(int i = 0 ;i<n;i++)
            {
                d[i][i]=1;
            }
            for(int i =n-2;i>=0;i--)
            {
                for(int j = i+1;j<n;j++)
                {
                    if(s[i]==s[j])
                    {
                        d[i][j] = d[i][j-1];
                    }
                    else
                    {
                        d[i][j] = 10000000;
                        for(int k = i;k<j;k++)
                        {
                            d[i][j] = min(d[i][j],d[i][k]+d[k+1][j]);
                        }
                    }
                }
            }
            return d[0][n-1];
        }
    };

发表评论取消回复

表情：

评论列表（有 0 条评论，88人围观）

还没有评论，来说两句吧...

相关阅读

相关 leetcode 644 奇怪的打印机

> 有台奇怪的打印机有以下两个特殊要求： > 打印机每次只能打印同一个字符序列。 > 每次可以在任意起始和结束位置打印新字符，并且会覆盖掉原来已有的字符。 > 给定

忘是亡心i/ 2023年08月17日 15:44/ 0 赞/ 55 阅读

相关 leetcode664. 奇怪的打印机【DP】

有台奇怪的打印机有以下两个特殊要求：打印机每次只能打印由同一个字符组成的序列。每次可以在任意起始和结束位置打印新字符，并且会覆盖掉原来已有的字符。给你一个字

痛定思痛。/ 2022年10月15日 10:54/ 0 赞/ 89 阅读

相关 664 奇怪的打印机（区间dp）

1. 问题描述：有台奇怪的打印机有以下两个特殊要求：打印机每次只能打印由同一个字符组成的序列。每次可以在任意起始和结束位置打印新字符，并且会覆盖掉原来已有的字符

妖狐艹你老母/ 2022年09月02日 08:08/ 0 赞/ 51 阅读

相关奇怪的电梯

include <bits/stdc++.h> using namespace std; int a[205],vis[205],r

雨点打透心脏的1/2处/ 2022年08月31日 00:44/ 0 赞/ 155 阅读

相关 NYOJ 664 数字整除

数字整除时间限制： 1000 ms | 内存限制： 65535 KB 难度： 2 描述定理：把一个至少两位的正整数的个位数字去掉，再从余下的数中减去个位数的5倍

布满荆棘的人生/ 2022年08月25日 01:54/ 0 赞/ 100 阅读

相关奇怪的比赛

某电视台举办了低碳生活大奖赛。题目的计分规则相当奇怪：每位选手需要回答10个问题（其编号为1到10），越后面越有难度。答对的，当前分数翻倍；答错了则扣掉与题号相同的分数

亦凉/ 2022年08月08日 13:59/ 0 赞/ 133 阅读

相关 leetcode 664. Strange Printer 奇怪的打印机+最小打印次数 + 动态规划DP

There is a strange printer with the following two special requirements: The printer can

浅浅的花香味﹌/ 2022年06月03日 07:44/ 0 赞/ 73 阅读

相关 map+DP leetcode446

如果数字序列由至少三个元素组成并且任何两个连续元素之间的差异相同，则称为算术序列。例如，这些是算术序列： 1，3，5，7，9 7，7,7，7 3，-1，-5，-9

以你之姓@/ 2022年05月15日 13:55/ 0 赞/ 68 阅读

相关奇怪的比赛

package Java2012大赛; / / 某电视台举办了低碳生活大奖赛。题目的计分规则相当奇怪：每位选手需要回

布满荆棘的人生/ 2022年03月20日 18:46/ 0 赞/ 186 阅读

相关 AcWing - 96. 奇怪的汉诺塔【DP】题解

目录 1.题目 2.代码 1.题目汉诺塔问题，条件如下： 1、这里有A、B、C和D四座塔。 2

桃扇骨/ 2021年07月24日 15:28/ 0 赞/ 253 阅读