推 rainkaras: 寶 大師 08/21 23:10
推 JIWP: 寶換一台印表機最快 08/21 23:11
→ oin1104: RPu4los8 08/21 23:13
→ oin1104: 我看這個人的 我覺得他講的不錯 08/21 23:13
→ DJYOMIYAHINA: 我也看他的 不過我是直接看github上的文字 08/21 23:14
→ oin1104: 他講的時候有畫圖 先不說他畫的好不好 他講的是挺好的 08/21 23:15
看著安沙寫的 還是沒能想到
dp(i,j) -> s[i:j]的答案
每次更新的時候遍歷 for k in [i+1,j]
若 s[k] = s[i]
則可以試著一次打印i:k as s[i]
然後加上dp(i,k-1)+dp(k+1,j)
因為這時s[i:k-1]以及s[k+1,j]還沒有打印好
我們只是先決定要打印一排s[i]
就根據這個規則遍歷下去
每次dp(i,j)，就遍歷i,j中間的character一次
然後稍微memorize一下
我其實只會寫recursive
要我bottom-up我反而完全不會寫
def strangePrinter(self, s: str) -> int:
n = len(s)
dp_mem = [[-1 for _ in range(n)] for _ in range(n)]
#init
for i in range(n):
dp_mem[i][i] = 1
def dp(i,j):
if j<i:
return 0
elif dp_mem[i][j] != -1:
return dp_mem[i][j]
cur_dp_val = 1+dp(i+1,j)
for k in range(i+1,j+1):
if s[k] == s[i]:
cur_dp_val = min(cur_dp_val, dp(i,k-1)+dp(k+1,j))
dp_mem[i][j] = cur_dp_val
return cur_dp_val
return dp(0,n-1)
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 125.229.37.69 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1724252920.A.021.html
※ 編輯: DJYOMIYAHINA (125.229.37.69 臺灣), 08/21/2024 23:13:04