刷
July-14-2019
日他妈好难啊
第一种做法，就是类似于palindrome-partition那样，枚举出所有可能，选一个substring数目最少的。
第二种做法DP，看到DP真几把绝望。
minCut[n]代表0~n的substring最少能切多少下，使所有substring都是palindrome
minCut[n]有2种可能
1 - 本身是palindrome, 那么minCut[n] = 0
2 - 本身不是，那它等于是0~(n-1)的substring又添加了最后一个char. 最后添加的字母肯定是palindrome，所以 minCut[n] = minCut[n-1] + 1
有人说，遇到这种情况怎么办，abacac (minCut[5])
abaca, minCut[4]=2: aba|a|c
minCut[5] = minCut[4] + 1 = 3，结果是错的，因为可以 aba|cac
于是，在刚才的2的情况下，minCut[n-1] + 1是minCut[n]的最差情况。。
实际上要遍历各种情况，分为左边和右边：
minCut[0] + 1~n
minCut[1] + 2~n
minCut[2] + 3~n
...
首先要判断右边是不是palindrome，不是的话不用看了。上面的abacac minCut[5]的最优解就在
minCut[2] + 3~5
判断palindrome 1~n也可以DP MEM来记录。
1~5, 2~5, 3~5判断是不是palindrome的时候，其实是先看两端是不是一样,
拿1~5来说，先看两端1和5是不是一样，一样的话再看中间2-4是不是一样，2-4在计算minCut[4]的时候已经算出来过，就不用重新算了。
讲是讲明白了，想我肯定是想不出来的。 看一刷的时候我说这个题不难，我为什么要装逼？为什么？
class Solution {
public int minCut(String s) {
if (s.length() <= 1) return 0;
int[] minCut = new int[s.length()];
boolean[][] isPalindrome = new boolean[s.length()][s.length()];
for (int i = 0; i < s.length(); i ++) {
int maxCutFrom0ToI = i;
int tempCut = maxCutFrom0ToI;
for (int j = 0; j <= i; j ++) {
// (j+1) >= (i-1) only 1 or 0 letter between j and i
if (s.charAt(i) == s.charAt(j) && ((j + 1) >= (i - 1) || isPalindrome[j + 1][i - 1])) {
isPalindrome[j][i] = true;
if (j == 0) {
// entire i~j is palindrome which requires 0 cut
tempCut = 0;
} else {
tempCut = Math.min(tempCut, minCut[j - 1] + 1);
}
}
}
minCut[i] = tempCut;
}
return minCut[s.length() - 1];
}
}
二刷
dp[i]表示从0 - i的最小切数。
dp[i]怎么算呢。。（他和前面的关系是什么？）
假如0 ~ i是回文，那最小切就是0.
能想到这写代码还是很不好写，我回头看有点弄不懂是怎么想出来的，实际解法比代码看起来要复杂的多。。感觉是用了2次DP。。
拿一段0 ~ n来说，他本身不是回文。 （是的话不用算了）
看看能不能分成0 ~ (i-1) | i ~ n 两段
左边用dp的mem来记忆能还是不能，右边楞判断，成功的话，就是dp[n] = dp[i-1] + 1
说是这么说，但是思路怎么来的很奇怪，我第一想法是
dp[0][i-1] + 1 + dp[i][n]这种二位的DP。。
简单地说这应该是个什么套路，但是我没总结出来。。
public class Solution {
public int minCut(String s) {
if (s.length() <= 1) return 0;
// from 0 to n
int[] dp = new int[s.length()];
boolean[][] mem = new boolean[s.length()][s.length()];
for (int i = 0; i < s.length(); i++) {
int from0toI = i;
for (int j = 0; j <= i; j++) {
if (s.charAt(i) == s.charAt(j) && (j + 1 >= i - 1 || mem[j+1][i-1])) {
mem[j][i] = true;
if (j == 0) {
from0toI = 0;
} else {
from0toI = Math.min(from0toI, dp[j - 1] + 1);
}
}
}
dp[i] = from0toI;
}
return dp[s.length() - 1];
}
}