131&132.md

都是二维 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;
};