看着安沙写的 还是没能想到
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)