# Python DP solution but TLE

• The algorithm uses list ptable to record whether a sub-string is a palindrome or not. ptable[i][j] == True means a sub-string starts from s[i] (inconclusive) to s[j] (inclusive) is a palindrome. Use list dp[i] to record the minimum number of palindromes within a sub-string start from s[i], dp[i] == 3 means a substring starts from s[i] (inconclusive) to the end (inclusive) has 3 palindromes and 3 is the minimum number. When ptable[i][j] == True case, we update list dp with dp[i]=min(dp[i],1+dp[j+1]). Finally the minimum cut is dp[0] - 1.

``````class Solution:
# @param s, a string
# @return an integer
def minCut(self, s):
n=len(s)
ptable=[[False for i in range(n)]for j in range(n)]
dp=[n-i for i in range(n+1)]
for i in range(n-1,-1,-1):
for j in range(i,n):
if s[i]==s[j] and (j-i<2 or s[i+1]==s[j-1]):
ptable[i][j]=True
dp[i]=min(dp[i],1+dp[j+1])
return dp[0]-1``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.