Posted on 2023-07-30 18:32
Uriel 阅读(30)
评论(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]