https://leetcode.com/problems/palindrome-partitioning-ii/description/
- 状态定义： dp[i] 为 min cut count for string s.sub(0, i);
- 状态转移方程： dp[i] = min of: s.substring(j, i) is palindrome ? dp[j] + 1 : dp[j] + (i - j) where j < i
- 初始化：dp length 为 s.length() + 1; dp[0] = 0; dp[1] = 0;
- 循环体: 双循环
- 返回 target：dp[len - 1]
Time Limit Exceeded even if with HashMap. "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabbaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"
class Solution {
HashMap<String, Boolean> map = new HashMap<>();
public int minCut(String s) {
if (s == null || s.length() == 0) {
return 0;
}
int len = s.length();
int[] minCuts = new int[len + 1];
for (int i = 0; i <= len; i++) {
minCuts[i] = i - 1;
}
for (int i = 1; i <= len; i++) {
for (int j = 0; j < i; j++) {
String sub = s.substring(j, i);
if (isPalindrome(sub)) {
minCuts[i] = Math.min(minCuts[i], minCuts[j] + 1);
}
}
}
return minCuts[len];
}
private boolean isPalindrome(String s) {
if (map.containsKey(s)) {
return map.get(s);
}
int left = 0, right = s.length() - 1;
while (left <= right) {
if (s.charAt(left) != s.charAt(right)) {
map.put(s, false);
return false;
}
left++;
right--;
}
map.put(s, true);
return true;
}
}
对 isPalindrome也使用了 DP 后通过了测试。其实，上面所使用的 HashMap 并不能提高运算效率或 Runtime，因为这里的 Hash 计算是需要遍历 string 所有 chars 来计算的，所以效率甚至不及不使用 Hash。
class Solution {
public int minCut(String s) {
if (s == null || s.length() == 0) {
return 0;
}
boolean[][] palindromeMap = buildPalindromeMap(s);
int len = s.length();
int[] minCuts = new int[len + 1];
for (int i = 0; i <= len; i++) {
minCuts[i] = i - 1;
}
for (int i = 1; i <= len; i++) {
for (int j = 0; j < i; j++) {
if (palindromeMap[j][i]) {
minCuts[i] = Math.min(minCuts[i], minCuts[j] + 1);
}
}
}
return minCuts[len];
}
private boolean[][] buildPalindromeMap(String s) {
int len = s.length();
boolean[][] palindromeMap = new boolean[len + 1][len + 1];
for (int i = 0; i < len; i++) {
palindromeMap[i][i + 1] = true;
palindromeMap[i][i] = true;
}
for (int i = 2; i <= len; i++) {
for (int j = 0; j < i - 1; j++) {
if (s.charAt(j) == s.charAt(i - 1) && palindromeMap[j + 1][i - 1]) {
palindromeMap[j][i] = true;
}
}
}
return palindromeMap;
}
}
上面 DP 对应 string 的方式，是 string split 的方式。这种方式可以描述为前 i 个字符。
上面解法使用了两次DP，第一次是对 s 所有 substring 进行判断是否为 palindrome；第二次是对 s 以 index 0 开始的所有substring 进行运算 minCuts；
From 九章：
state: f[i]”前i”个字符组成的子字符串需要最少 几次cut(最少能被分割为多少个字符串-1)
function: f[i] = MIN{f[i], f[j]+1}, j < i && j+1 ~ i这一 段是一个回文串
intialize: f[i] = i - 1 (f[0] = -1) answer: f[s.length()]
