?LeetCode刷題實(shí)戰(zhàn)132：分割回文串 II
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.
題意
示例:
輸入: "aab"
輸出: 1
解釋: 進(jìn)行一次分割就可將 s 分割成 ["aa","b"] 這樣兩個(gè)回文子串。
解題
dp[i-1]為子串s[0:i-1]（前閉后閉）的最小分割次數(shù)，推出dp[i]的轉(zhuǎn)移方程。首先，如果
s[0:i]本身是一個(gè)回文串，那么不需要分割，dp[i] = 0；如果
s[0:i]不是回文串，那么我們需要枚舉以s[i]結(jié)尾的回文串，從1到i的索引j，判斷s[j:i]是不是回文串，如果是，則dp[i]=dp[j-1]+1，即在前j-1個(gè)字符串的基礎(chǔ)上多一次切割。枚舉所有可能的j，取最小值。不可以逐次判斷是否是回文串，會(huì)超時(shí)，因此回文串的判斷也采取動(dòng)態(tài)規(guī)劃的思想。如果一個(gè)字符串
s[i:j]是回文串，那么其子串s[i+1:j-1]也是回文串。因此，dp[i][j]表示子串s[i:j]是否是回文串，我們枚舉字符串子串的長(zhǎng)度，再枚舉子串的起始位置，填充dp。
class?Solution(object):
????def?minCut(self, s):
????????"""
????????:type s: str
????????:rtype: int
????????"""
????????l = len(s)
????????dpPart = [[False]*l for?_ in?range(l)]
????????dp = [i for?i in?range(l)]
????????# 判斷回文串，填充dpPart
????????# 枚舉子串長(zhǎng)度
????????for?length in?range(l):
????????????# 枚舉子串開(kāi)始位置，length==0表示子串長(zhǎng)度為1
????????????for?i in?range(l):
????????????????j = i + length
????????????????if?j >= l:
????????????????????break
????????????????if?length == 0:
????????????????????dpPart[i][j] = True
????????????????elif?length == 1:
????????????????????dpPart[i][j] = (s[i] == s[j])
????????????????else:
????????????????????dpPart[i][j] = dpPart[i+1][j-1] and?(s[i] == s[j])
????????# 填充dp
????????for?i in?range(1, l):
????????????if?dpPart[0][i]:
????????????????dp[i] = 0
????????????????continue
????????????for?j in?range(1, i+1):
????????# 枚舉以s[i]結(jié)尾的回文串
????????????????if?(dpPart[j][i]):
????????????????????dp[i] = min(dp[i], dp[j - 1] + 1)
????????return?dp[l - 1]