Posted on 2023-07-30 18:32
Uriel 閱讀(51)
評論(0) 編輯 收藏 引用 所屬分類:
DP 、
閑來無事重切Leet Code
給出一列字符串，一臺打字機每次可以打出一串相同的字符，若想打印aba，可以先打印aaa然后打印b覆蓋中間的a，問打印完該串字符串要打印幾次，DP，思路參考 ->
1 #664
2 #Runtime: 444 ms (Beats 100%)
3 #Memory: 13.2 MB (Beats 100%)
4
5 class Solution(object):
6 def strangePrinter(self, s):
7 """
8 :type s: str
9 :rtype: int
10 """
11 n = len(s)
12 dp = [[101] * n for _ in range(n)]
13 for i in range(n):
14 dp[i][i] = 1
15 for l in range(2, n + 1):
16 for i in range(n - l + 1):
17 j = i + l - 1
18 dp[i][j] = dp[i + 1][j] + 1
19 for k in range(i + 1, j + 1):
20 if s[i] == s[k]:
21 dp[i][j] = min(dp[i][j], dp[i][k - 1] + (dp[k + 1][j] if j != k else 0))
22 return dp[0][n - 1]