Given a string s, partition s such that every substring of the partition is a palindrome.
Return the minimum cuts needed for a palindrome partitioning of s.
For example, given s = "aab",
Return 1 since the palindrome partitioning ["aa","b"] could be produced using 1 cut.
定义状态 f(i,j) 表示区间 [i,j] 之间最小的 cut 数，则状态转移方程为
f(i, j) = min { f(i, k) + f(k + 1, j) } , i <=k <= j, 0 < i <= j <= n
我们求解的是整个字符串的最小cut数，可以从字符串的头开始，也可以从尾部开始
[LeetCode] Palindrome Partitioning II,布布扣,bubuko.com
[LeetCode] Palindrome Partitioning II
原文：http://www.cnblogs.com/diegodu/p/3853537.html