132. Palindrome Partitioning II
这题的思路多了一重，先弄出dp[i][j] 代表 s[i:j+1]是否是palindrome。然后在用一个d[i]表示 从 s[0:i+1]最少要切多少刀。d[i] = min(d[i], d[j-1]+1 if dp[j][i] is True for j in 0~i)
在实际做的时候，只想到了第一重，第二重d[i] 没想出来，其实也是有点着急了。再花点时间应该也还是能想出来的。
对于第一重dp来说又是一个对角线结构。可以用k距离来做，j = i + k 这样就不用把i的循环倒序了。
class Solution(object):
def minCut(self, s):
"""
:type s: str
:rtype: int
"""
dp = [[False for _ in range(len(s))] for _ in range(len(s))]
for i in range(len(s))[::-1]:
for j in range(i, len(s)):
if i == j:
dp[i][j] = True
elif j - i == 1:
dp[i][j] = s[i] == s[j]
else:
dp[i][j] = (s[i] == s[j]) and dp[i+1][j-1]
d = [sys.maxint for _ in range(len(s))]
# dp[i] is min cut for s[0~i] include i
for i in range(len(s)):
if dp[0][i]:
d[i] = 0
for i in range(len(s)):
for j in range(i+1):
if dp[j][i]: # j~i includsive is true
d[i] = min(d[i], d[j-1]+1)
return d[-1]
