推 Smallsh: 大師 08/21 20:10
推 smart0eddie: 現在一台印表機幾千塊而已換一台吧 08/21 20:10
→ JIWP: 對阿換一台吧,白癡leetocde 08/21 20:11
※ 編輯: JIWP (42.72.129.51 臺灣), 08/21/2024 20:16:29
DP HARD 我直接看答案最快
664. Strange Printer
有一台壞掉的印表機
只能做到下面兩個操作
(1)印出一串相同的字串
(2)把字串中一個字元改成另外一個
給你s，請問最少要幾步可以印出s
思路:
換一台印表機最快
這題的規律就是當子字串s[i:j]頭尾的字元相同
那子字串s[i:j]的最小步數會跟s[i+1:j]相同
用2D DP矩陣紀錄s[i:j]的最小步數
這樣就找到狀態轉移方程式
當s[i]==s[k]時
dp[i][j]=min(dp[i][j],dp[i+1][k-1]+dp[k][j])
就這樣用3個for迴圈去跑遍所有子字串、k的組合
golang code :
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 > -1; i-- {
dp[i][i] = 1
for j := i + 1; j < n; j++ {
dp[i][j] = 1 + dp[i+1][j]
for k := i + 1; k <= j; k++ {
if s[i] == s[k] {
dp[i][j] = min(dp[i][j], dp[i+1][k-1]+dp[k][j])
}
}
}
}
return dp[0][n-1]
}
--
https://i.imgur.com/r9FBAGO.gif
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 42.72.129.51 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1724242181.A.DAF.html