Uriel's Corner

Research Associate @ Harvard University / Research Interests: Computer Vision, Biomedical Image Analysis, Machine Learning
posts - 0, comments - 50, trackbacks - 0, articles - 594
给出一列字符串,一台打字机每次可以打出一串相同的字符,若想打印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]

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理