t********n
发帖数: 611 | 1 这个解法明明是 n ^2， 死活通不过，请大神帮忙看看哪里可以改进！
class Solution:
# @param s, a string
# @return an integer
# @dfs time out
# @dp is how many palindromes in the word
def minCut(self, s):
dp = [0 for i in range(len(s)+1)]
p = [[False for i in range(len(s))] for j in range(len(s))]
for i in range(len(s)+1):
dp[i] = len(s) - i
for i in range(len(s)-1, -1, -1):
for j in range(i, len(s)):
if s[i] == s[j] and (((j - i) < 2) or p[i+1][j-1]):
p[i][j] = True
dp[i] = min(1+dp[j+1], dp[i])
return dp[0]-1 |
|
