Re: [閒聊] 每日leetcode
看著安沙寫的 還是沒能想到
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
推
08/21 23:10,
1年前
, 1F
08/21 23:10, 1F
推
08/21 23:11,
1年前
, 2F
08/21 23:11, 2F
推
08/21 23:13,
1年前
, 3F
08/21 23:13, 3F
→
08/21 23:13,
1年前
, 4F
08/21 23:13, 4F
→
08/21 23:13,
1年前
, 5F
08/21 23:13, 5F
→
08/21 23:14,
1年前
, 6F
08/21 23:14, 6F
→
08/21 23:15,
1年前
, 7F
08/21 23:15, 7F
討論串 (同標題文章)
以下文章回應了本文：
完整討論串 (本文為第 749 之 1548 篇)：