动态规划是将问题转化为子集问题，缩小问题的规模，也就是说先从最小的子集开始计算，由小的状态得出更大集合的状态．而在本题中，如何将问题分割成子状态呢？将一个字符串切割成两部分，如果右边是回文子串，那么需要的切点就为：左边的子串切点+1，如果右边非回文，则需要的切点就为：左边子串切点+1＋右边子串长度-1．这样就将问题分解成了子状态＋一个已知状态．我们只需要枚举将字符串分割的切点，取一个最优的解即可计算一个字符串的解，然后这个解又会作为子集解用于解决更大规模的问题，直到将整个问题解决．

 

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