动态规划 leetcode-664 奇怪的打印机

最新推荐文章于 2024-05-22 16:28:54 发布

mydoubts

最新推荐文章于 2024-05-22 16:28:54 发布

阅读量280

点赞数

分类专栏： leetcode

本文链接：https://blog.csdn.net/mydoubts/article/details/106100088

版权

leetcode 专栏收录该内容

23 篇文章

订阅专栏

1.题目：

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

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

示例 1:

输入: “aaabbb”
输出: 2
解释: 首先打印 “aaa” 然后打印 “bbb”。
示例 2:

输入: “aba”
输出: 2
解释: 首先打印 “aaa” 然后在第二个位置打印 “b” 覆盖掉原来的字符 ‘a’。

2.解题

难度:困难，假设dp代表第l个位置到r个位置之间的最小打印次数，对于任何的dp[l][r],都有dp[l][r] = dp[l+1][r] + 1，因为l肯定是第一个打印的，
对应每一个长度的i,假设i=1时，l的位置可以是0到n-i,假设l取0,那么r=0+i-1=0,因此所有的i=1,有l=r，对应位置的dp[l][r]就等于1
假设i=4,l=0时,r=0+4-1=3,dp[0][3]=dp[1][3]+1,k可以取1、2、3,k遍历是找到最小的次数，要找到按照k划分还是维持当前dp[l][r]值那个最小

class Solution:
    def strangePrinter(self, s: str) -> int:
        if not s:
            return 0
        n = len(s)
        dp = [[0]*(n+1) for i in range(n+1)]
        for i in range(1, n+1):
            for l in range(n-i+1):
                # 计算的时候保证小的已经算出来了
                r = l + i -1
                dp[l][r] = dp[l+1][r] + 1
                for k in range(l+1, r+1):
                    if s[k] == s[l]:
                        dp[l][r] = min(dp[l][r], dp[l][k-1]+dp[k+1][r])
        return dp[0][n-1]