力扣664. 奇怪的打印机
阿巩
一切已妥当，绝不咕咕！
阿巩想死你们了！今日起恢复日更。由于被再三嘱咐不能熬夜，如果当天时间充裕的话，会学习并及时输出干货；时间比较紧则在次日上班前更新一道数据结构或算法题。日拱一卒，我们开始吧！
在之前分享动态规划的文章中，我们说动态规划主要是用于解决求最值的问题的。它希望上一个状态和下一个状态之间有关系而且连续。对于本题来说求打印次数有以下几种情况：
1、只有一个字符a：1次
2、打印字符ab：2次
3、打印字符aba：2次
4、打印字符abab：3次
我们可以看出两点规律：首先判断区间两边字符是否相同，如果相同（aba），它的打印次数与更小一层的子区间结果一致；如果不相同（abab）那么将对剩区间内的组合方式进行枚举，并取出最小值。
状态定义：[i, j]表示从i到j的一个区间，dp[i][j]表示最少打印次数。
状态转移方程：如果s[i] == s[j]即区间两边字符相同，那么dp[i][j] = dp[i][j-1]即与更小一层的子区间结果一致；如果s[i] 和s[j]不相等，则进行枚举并返回最小值 min(dp[i][j], dp[i][k] + dp[k+1][j])。
初始状态：n 是字符串的长度。dp数组抽象成一个n * n 的矩阵。dp = [[n] * n for _ in range(n)]
返回值：dp[0][n-1]
Python的区间DP代码如下
def strangePrinter(s):
n = len(s)
dp = [[n] * n for _ in range(n)]
for i in range(n-1, -1, -1):
dp[i][i] = 1
for j in range(i+1, n):
if s[i] == s[j]:
dp[i][j] = dp[i][j-1]
else:
for k in range(i, j):
dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j])
return dp[0][n-1]
s = "abab"
print(strangePrinter(s)) # 3用GO语言实现代码如下
package main
func strangePrinter(s string) int {
n := len(s)
dp := make([][]int, n)
for i := 0; i < n; i++{
dp[i] = make([]int, n)
}
for i := n-1; i >= 0; i-- {
for j := i; j < n; j++ {
if i == j {
dp[i][j] = 1
continue
}
if s[i] == s[j] {
dp[i][j] = dp[i][j-1]
continue
}
min := j-i+1
for k := i; k < j; k++ {
tmp := dp[i][k] + dp[k+1][j]
if tmp < min {
min = tmp
}
}
dp[i][j] = min
}
}
return dp[0][n-1]
}
func main() {
s := "abab"
println(strangePrinter(s)) // 3
}除了区间DP，本题还可以使用记忆化DFS+剪枝的思路理解，代码实现与dp类似。
预处理：将连续的，由相同字符组成的子串看做一个。比如"aaabbb"和"ab"是没有区别的。
递推：如果j和i是相同的，那么打印i到j和打印i到j-1所需的次数是一样的；如果i和j不同，找出所有拆分方法中的最小值。
from functools import lru_cache
def strangePrinter(s):
printer = [s[0]]
for i in range(1, len(s)):
if s[i] != s[i-1]:
printer.append(s[i])
@ lru_cache(None)
def dfs(i, j):
if i > j:
return 0
elif i == j:
return 1
if printer[i] == printer[j]:
return dfs(i, j-1)
return min(dfs(i, k) + dfs(k+1, j) for k in range(i, j))
return dfs(0, len(printer)-1)
s = "aabaaab"
print(strangePrinter(s)) # 3END
腾讯云开发者
