看著安沙寫的 還是沒能想到
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)