```
class Solution(object):
def minCut(self, s):
"""
:type s: str
:rtype: int
"""
if s is None or len(s) <= 1:
return 0
m = len(s)
dp = [[False] * m for i in xrange(m)]
for width in xrange(m):
for i in xrange(m - width):
j = i + width
dp[i][j] = (width <= 1 or dp[i + 1][j - 1]) and s[i] == s[j]
dpp = [-1] * (m + 1)
for i in xrange(m):
minvalue = i
for j in xrange(i + 1):
if dp[j][i]:
minvalue = min(minvalue, dpp[j])
dpp[i + 1] = minvalue + 1
return dpp[-1]
```