leetcode664. 奇怪的打印机【DP】

痛定思痛。 2022-10-15 10:54 183阅读 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 条评论，183人围观）

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

相关阅读

相关 leetcode 644 奇怪的打印机

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

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

相关 Java实现 LeetCode 664 奇怪的打印机（DFS）

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

落日映苍穹つ/ 2023年07月21日 11:10/ 0 赞/ 41 阅读

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

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

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

相关 Leetcode 97. 交错字符串(DP)

题目重述给定三个字符串 s1、s2、s3，请你帮忙验证 s3 是否是由 s1 和 s2 交错组成的。两个字符串 s 和 t 交错的定义与过程如下，其中每个字符串

喜欢ヅ旅行/ 2022年09月08日 03:44/ 0 赞/ 249 阅读

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

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

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

相关 NYOJ 664 数字整除

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

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

相关 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 赞/ 145 阅读

相关 map+DP leetcode446

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

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

相关 LeetCode-62 不同路径（dp）

一个机器人位于一个 m x n 网格的左上角（起始点在下图中标记为“Start” ）。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Fi

Love The Way You Lie/ 2022年04月24日 02:36/ 0 赞/ 285 阅读

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

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

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