动态规划, 用isPal记录子串是不是回文串, isPal[i][j] == true含义是从s[i]到s[j]的子串(包含起点终点)是回文串。用minPalNum记录以s[0]为起点的子串包含的最少的回文串的个数, minPalNum[i] == 3 含义是从s[0]到s[i]的子串(包含起点终点)中回文串的最小数目是3个。当遇到一个isPal[i][j] == true的情况, 就更新minPalNum。最后minPalNum[lenS] - 1即为所求。

Dynamic programming. Use "isPal" to record whether a substring is a palindrome or not, "isPal[i][j] == true" means a substring starts from s[i] (includsive) to s[j] (inclusive) is a palindrome. Use "minPalNum" to record the minimum number of palindromes within a substring start from s[0], "minPalNum[i] == 3" means a substring starts from s[0] (included) to s[i] (included) has 3 palindromes and 3 is the minimum number. When we meet a "isPal[i][j] == true" case, we update minPalNum. Finally the result is minPalNum[lenS] - 1.

class Solution:
    # @param s, a string
    # @return an integer
    def minCut(self, s):
        lenS = len(s)
        isPal = [[False for j in xrange(lenS)] for i in xrange(lenS)]
        minPalNum = [i + 1 for i in xrange(lenS)]
        for j in xrange(lenS):
            for i in reversed(xrange(j + 1)):
                if s[i] == s[j] and ( j - i <= 1 or isPal[i + 1][j - 1] == True):
                    isPal[i][j] = True
                    minPalNum[j] = min(minPalNum[j], minPalNum[i - 1] + 1) if i > 0 else min(minPalNum[j], 1) # i == 0
        return minPalNum[lenS - 1] - 1