Palindrome Partitioning II
这道题我称之为究极动态规划，原因也很简单，它其实就是把一个中等偏难的DP和一个中等偏容易的DP结合在一起，然后就变成一个比较变态的题了，关键在于人的思维很难会意识到在一道题里面要进行两次不同形式的DP去解决问题，首先，第一个DP也是相对难的DP是通过一个n * n的bool矩阵去记录整个输入字符串各个区间是否为对称字符串，明显地，所有i==j的点都是对称的，因为一个字符串都是对称的，所以这也是base case，另外一个字符串是不是对称可以转化为一个状态方程如下
string[i : j + 1] is Palindrome?
if string[i] == string[j] and dp[i + 1][j - 1] == True:
Yes
else:
No
可以看到这就是Longest Palindromic Substring的DP解题方法
但是这道题又有一个巨坑，在于这种区间类的动态规划人直觉上是往记忆化搜索去思考的，但是这道题如果用记忆化搜索的方法去做会TLE（原因至今不明），所以只能转成用矩阵递推的方式，而这里的递推和坐标类非常不一样，在于内层循环点是从当前行和对角线相交的点开始从中间往天花板递推的，另外在两个坐标只差一的时候也属于base case，因为你只要判断两个字符串是不是相等就能知道是否对称了
上面是第一个判断区间字符串对称的DP，在做完之后，我们就得到了一个可以判断一个字符串任意区间是否为对称的矩阵，这样我们就可以利用LIS的思路去判断一个区间内最少可以被切割成几段了，因为有了这个矩阵，我们只需要O(1)时间就可以判断了，如果没有之前的DP，我们就只能写一个朴素的判断对称的函数，那样相当于又多了一层O(n)的循环，导致TLE，下面是整个代码
class Solution(object):
def minCut(self, s):
"""
:type s: str
:rtype: int
"""
n = len(s)
ref = [([False] * n) for _ in xrange(n)]
for i in xrange(n):
for j in xrange(i, -1, -1):
if i == j:
ref[j][i] = True
elif j + 1 == i:
ref[j][i] = (s[j] == s[i])
elif s[j] == s[i]:
ref[j][i] = ref[j + 1][i - 1]
else:
ref[j][i] = False
res = [0] * n
for i in xrange(n):
q = i + 1
for j in xrange(i):
if ref[j][i]:
q = min(q, res[j - 1] + 1)
res[i] = min(q, res[i - 1] + 1)
return res[n - 1] - 1
上面的ref矩阵是使用了矩阵的右上部分，还可以使用矩阵的左下部分来做
class Solution(object):
def minCut(self, s):
"""
:type s: str
:rtype: int
"""
n = len(s)
dp = [[False] * n for _ in xrange(n)]
for i in xrange(n):
for j in xrange(i + 1):
if s[i] == s[j] and (i - j <= 2 or dp[i - 1][j + 1]):
dp[i][j] = True
distance = [0] * n
for i in xrange(n):
distance[i] = i + 1
for j in xrange(i + 1):
if j == 0 and dp[i][j]:
distance[i] = 1
if dp[i][j]:
distance[i] = min(distance[i], distance[j - 1] + 1)
return distance[n - 1] - 1
还有一种只用一次DP解决问题的方法