都是二维 dp
131
/**
* @param {string} s
* @return {string[][]}
*/
const partition = function (s) {
const isPalindrome = s => s === s.split('').reverse().join('');
const n = s.length;
if (n <= 0) return [];
const dp = new Array(n).fill(0).map(() => new Array());
dp[0] = [[s[0]]];
for (let i = 1; i < n; i++) {
if (isPalindrome(s.slice(0, i + 1))) dp[i].push([s.slice(0, i + 1)]);
for (let j = 0; j < i; j++) {
if (dp[j].length > 0 && isPalindrome(s.slice(j + 1, i + 1)))
dp[j].forEach(arr => dp[i].push([...arr, s.slice(j + 1, i + 1)]));
}
}
return dp[n - 1];
};
132
const partition = function (s) {
const isPalindrome = s => s === s.split('').reverse().join('');
const n = s.length;
const dp = new Array(n).fill(Number.MAX_SAFE_INTEGER);
dp[0] = 0;
for (let i = 1; i < n; i++) {
if (isPalindrome(s.slice(0, i + 1))) {
dp[i] = 0;
continue;
}
for (let j = 0; j < i; j++) {
if (dp[j] !== Number.MAX_SAFE_INTEGER && isPalindrome(s.slice(j + 1, i + 1)))
dp[i] = Math.min(dp[i], dp[j] + 1);
}
}
return dp[n - 1];
};
var minCut = function (s) {
if (s.length <= 1) return 0;
const r = partition(s);
return r;
};