DFS不能AC
这题我想像 131题那样dfs把所有解找到然后找到需要cut最短的那一个，用一个全局变量保存minCut，每次解出来之后判断是否需要更新。我自己测试了没问题，但提交的时候TLE了。
int minCut;
public int minCut(String s) {
if (s == null || s.equals("")) return 0;
minCut = s.length() - 1;
backtrack(new ArrayList<String>(), s, 0);
return minCut;
}
public void backtrack(List<String> tempList, String s, int start) {
if (start == s.length()) {
if (tempList.size() - 1 < minCut) minCut = tempList.size() - 1;
return;
}
for (int i = start; i < s.length(); i++) {
if (isPalindrome(s, start, i)) {
tempList.add(s.substring(start, i + 1));
backtrack(tempList, s, i + 1);
tempList.remove(tempList.size() - 1);
}
}
}
private boolean isPalindrome(String s, int low, int high) {
while (low <= high) {
if (s.charAt(low++) != s.charAt(high--)) return false;
}
return true;
}
我也有考虑能不能用带返回值的dfs来写，但是想不到，因为跟boolean不同，int需要代入到下一次递归。
这题不能用131的dfs，摘抄一段code ganker的解释：
做过Word Break的朋友可能马上就会想到，其实两个问题非常类似，当我们要返回所有结果（Palindrome Partitioning和Word Break II）的时候，使用动态规划会耗费大量的空间来存储中间结果，所以没有明显的优势。而当题目要求是返回某个简单量（比如Word Break是返回能否切割，而这道题是返回最小切割数）时，那么动态规划比起brute force就会有明显的优势。
动态规划
这题的动态规划有点难，它需要一个二维数组和一个一维数组。
一维数组minCut[i]保存着s从头开始到i切分成palindrome需要的minCut；
二维数组pal[j][i]保存着从j到i的substring是不是palindrome。（i<n ; j<=i，也就是说用j把0到i的长度再拆分，判断j到i是不是pal，如果是，那j到i显然就不需要切了）
看着挺难了，理解了也就那么回事。但是这种题目让我自己想真是完全想不到。难点不仅在于两个状态的定义，转移方程也很难想到。另外，对于palindrome的判断，
s.charAt(i) == s.charAt(j) && pal[j+1][i-1])
这句要写在
(s.charAt(i) == s.charAt(j) && i - j <= 1
之后，否则i = 0会出现outofbounds。
还有i - j <= 1写成i - j <= 2也能AC，因为两个相同的数中间夹一个数也是palindrome。
public int minCut(String s) {
if (s == null || s.length() == 0) return 0;
boolean[][] pal = new boolean[s.length()][s.length()];
int[] minCut = new int[s.length()];
for (int i = 0; i < s.length(); i++) {
minCut[i] = i;
for (int j = 0; j <= i; j++) {
if ((s.charAt(i) == s.charAt(j) && i - j <= 1 ||
s.charAt(i) == s.charAt(j) && pal[j+1][i-1])) {
pal[j][i] = true;
//因为j-1可能会outofbound，所以把j=0单独拎出来。也可以把转移方程倒过来写了，就是从后往前切。
if (j > 0) {
minCut[i] = Math.min(minCut[i], minCut[j - 1] + 1);
} else {
//j == i的时候切0刀
minCut[i] = 0;
}
}
}
}
return minCut[s.length() - 1];
}
ref：
- http://www.programcreek.com/2014/04/leetcode-palindrome-partitioning-ii-java/
- https://mp.weixin.qq.com/s?__biz=MzA5MzE4MjgyMw==&mid=2649455553&idx=1&sn=9e94d5c9d76d53b052a6c6dbafd5f040&chksm=887e15c9bf099cdfe22780affcd3246294fa47adf1bd66ac1da10fe886027ca0c2656bc7c29e&mpshare=1&scene=1&srcid=0317MZTcO3q6FemAIsR3wS3H&key=9089d717e4fbaa823f82f97f3e6605e58c4fb92d717f6136f1e33846c2814e1bbb1b818ca5fb4f9d80a6824fe06a840c15c7a64052c9e2c74d48feade171acd5ba5ccc02f95afb3a02617dada4bce6b4&ascene=0&uin=MTUyMzg3NjAwMA%3D%3D&devicetype=iMac+MacBookAir7%2C1+OSX+OSX+10.12.3+build(16D32)&version=12020010&nettype=WIFI&fontScale=100&pass_ticket=0AiIToHJN8yqpuqRAsA5PaaQMJr8KtvlnZ2EqkX0zx%2BEZweRvHKyF%2ByjmycpUbVn
