leetcode 644 奇怪的打印机

忘是亡心i 2023-08-17 15:44 98阅读 0赞

> 有台奇怪的打印机有以下两个特殊要求：  
> 打印机每次只能打印同一个字符序列。  
> 每次可以在任意起始和结束位置打印新字符，并且会覆盖掉原来已有的字符。  
> 给定一个只包含小写英文字母的字符串，你的任务是计算这个打印机打印它需要的最少次数。  
> 来源：力扣（LeetCode）  
> 链接：[https://leetcode-cn.com/problems/strange-printer][https_leetcode-cn.com_problems_strange-printer]

思路：  
1.首先这是区间动态规划  
2.f\[i\]\[j\]表示闭区间从i到j印刷最少次数  
3.区间从1开始枚举，因为1是base case 我们可以单独拿出来处理f\[i\]\[i\]=1  
4.区间从2开始之后，就会比之前区间为1的时候多1个元素，我们可以用k来分割成两个小区间相加即可，注意这里有一个特殊情况，如果新进来的元素和端点元素相等那麽f\[i\]\[j\]=f\[i+1\]\[j\]或f\[i\]\[j-1\]

class Solution {
    public:
        int strangePrinter(string s) {
            if(!s.size())return 0;
            vector<vector<int>> f(s.size()+1,vector<int>(s.size()+1,1e9));
            for(int i=0;i<s.size();++i)f[i][i]=1;
            for(int len=2;len<=s.size();++len){
                for(int i=0;i+len-1<s.size();++i){
                    int j=i+len-1;
                    if(s[i]==s[j])f[i][j]=f[i+1][j];
                    else if(s[j]==s[j-1])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[k+1][j]);
                        }
                    }
                }
            }
            return f[0][s.size()-1];
        }
    };

转载于:https://www.cnblogs.com/clear-love/p/11455055.html

[https_leetcode-cn.com_problems_strange-printer]: https://leetcode-cn.com/problems/strange-printer

发表评论取消回复

表情：

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

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

相关阅读

相关 leetcode 644 奇怪的打印机

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

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

相关奇怪的d问题

代码如下: int i; int p = &i; int f= { return p; } return &f;

客官°小女子只卖身不卖艺/ 2022年11月13日 06:22/ 0 赞/ 153 阅读

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

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

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

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

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

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

相关奇怪的电梯

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

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

相关奇怪的比赛

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

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

相关 python-----奇怪的国家

有一个奇怪的国家，里面的国民对于事情的态度永远只有两面。当两个人遇到一起讨论一个事情的时候——两个持赞同观点的人遇到一起后会对这个事情都继续赞同；一个持赞同观点的人遇到

桃扇骨/ 2022年06月08日 06:53/ 0 赞/ 160 阅读

相关奇怪的比赛

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

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

相关一个奇怪的现象

我删除了在windows中创建的性能收集器。随之oracle的数据文件就消失了。这个现象是说明了我删除windows的性能收集器，就自带的把oracle的数据文件给删除了吗

逃离我推掉我的手/ 2021年12月14日 08:07/ 0 赞/ 231 阅读

相关好奇怪的游戏

题目背景《爱与愁的故事第三弹·shopping》娱乐章。调调口味来道水题。题目描述爱与愁大神坐在公交车上无聊，于是玩起了手机。一款奇怪的游戏进入了爱与愁

清疚/ 2021年11月13日 15:12/ 0 赞/ 248 阅读