【LeetCode】664. 奇怪的打印机

奇怪的打印机

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

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

示例1

输入：s = "aaabbb"
输出：2
解释：首先打印 "aaa" 然后打印 "bbb"。
复制代码

示例2

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

思路

• 一般使用动态规划来解决最多、最少问题。
• dp[i][j]来表示区间[i,j]之间的最少打印次数
• 比如“a”,只有一个字符，则需要打印1次
• 比如“ab”,只有两个字符，则需要打印2次
• 比如“aba”，有三个字符，则需要打印2次，先打印“aaa”,再打印中间的“b”。
• 比如“abab”,有四个字符，则需要划分为更小的区间分情况获取最少的打印次数。如下分析：先打印“a”,再打印“bab”,打印次数为1+2=3；先打印“ab”,再打印“ab”,打印次数为2+2=4；先打印“aba”,再打印“b”,打印次数为2+1=3。综上上述，打印次数最少为3。
• 根据上述分析，分为两个情况讨论：

当s[i]==s[j]时，dp[i][j]=dp[i][j-1];

当s[i]!=s[j]时，dp[i][j]=min(d[[i][j],dp[i,k]+dp[k+1][j])

• 由于存在只有一个字符时，则需要打印次数为1。即dp[i][j]=1。
• 在本题中，可以分为从前往后分析（如解法二）和从后往前分析（如解法一）。

解法一

func strangePrinter(s string) int { // 从后往前分析
    dp:=make([][]int,len(s)) // 定义二维动态数组，dp[i][j]来存放区间[i,j]之间的最少打印次数
    for i:=0;i<len(dp);i++{
       dp[i]=make([]int,len(s))
    }
    for i:=len(s)-1;i>=0;i--{ // 从后往前遍历
        dp[i][i]=1 // 只包含一个字符，则初始化dp[i][i]=1
        for j:=i+1;j<len(s);j++{ // 确定[i,j]之间的最少使用次数
            if s[i]==s[j]{ // 如果相等，则s[j]不影响区间[i,j]的使用次数，和之前的[i,j-1]相等
                dp[i][j]=dp[i][j-1]
            }else{ // 如果不想等，则需要划分更小的区间寻找最小使用次数
                dp[i][j]=math.MaxInt64 //求最小值，因此使用最大值来初始化dp[i][j]
                for k:=i;k<j;k++{ // 划分区间[i,j]
                    dp[i][j]=minValue(dp[i][j],dp[i][k]+dp[k+1][j])
                }
            }
        }
    }
    return dp[0][len(s)-1] // 返回整个区间[0,len(s)-1]的最小使用次数
}

func minValue(a,b int)int{
    if a<b{
        return a
    }
    return b
}
复制代码

解法二

func strangePrinter(s string) int { // 从前往后分析
    dp:=make([][]int,len(s)) // 定义二维动态数组，dp[i][j]来存放区间[i,j]之间的最少打印次数
    for i:=0;i<len(s);i++{
        dp[i]=make([]int,len(s))
    }
    for i := 0; i < len(s); i++ { // 从前往后分析
        dp[i][i] = 1 // 只包含一个字符，则初始化dp[i][i]=1
        for j := i-1; j >= 0; j-- { // 确定区间[j,i]之间的最少使用次数
            if(s[i] == s[j]){ // 如果相等，则s[j]不影响区间[i,j]的使用次数，和之前的[i,j-1]相等
                dp[j][i] = dp[j+1][i]
            }else{ // 如果不想等，则需要划分更小的区间寻找最小使用次数
                dp[j][i]=math.MaxInt64 //求最小值，因此使用最大值来初始化dp[i][j]
                for k:=i; k > j; k-- { // 划分区间[j,i]
                    dp[j][i] = min(dp[j][i], dp[j][k-1] + dp[k][i])
                }
            }
        }
    }
    return dp[0][len(s)-1] // 返回整个区间[0,len(s)-1]的最小使用次数
}
func min(a,b int)int{
    if a>b{
        return b
    }
    return a
}
复制代码