动态规划、记忆化递归：求解《131. 分割回文串》《剑指 Offer II 086. 分割回文子字符串》《132. 分割回文串 II》《剑指 Offer II 094. 最少回文分割》《1278. 分割回文串 III》

用动态规划、记忆化递归求解《131. 分割回文串》《剑指 Offer II 086. 分割回文子字符串》《132. 分割回文串 II》《剑指 Offer II 094. 最少回文分割》和《1278. 分割回文串 III》

模板

动态规划 · 判断回文

const n = s.length
const dp = Array.from({length : n}, _ => new Uint8Array(n).fill(1)) // *注意：fill(1)
for (let i = n; i--;) {<br>
  for (let j = i + 1; j < n; j++) {
    dp[i][j] = s[i] === s[j] ? dp[i + 1][j - 1] : 0
  }
}

动态规划 · 变成回文，需要替换字符数

const n = s.length
const cost = Array.from({length : n}, _ => new Uint8Array(n)）
for (let i = n; i--;) {<br>  for (let j = i + 1; j < n; j++) {<br>
    cost[i][j] = cost[i + 1][j - 1] + (s[i] === s[j] ? 0 : 1)
  }
}

递归 · 记忆化 · 判断回文

const n = s.length
const h = Array.from({length : n}, _ => new Int8Array(n))
const isPalindrome = (i, j, s) => {
  if (h[i][j] !== 0) return h[i][j]
  if (i >= j) h[i][j] = 1
  else if (s[i] === s[j]) h[i][j] = isPalindrome(i + 1, j - 1)
  else h[i][j] = -1
  return h[i][j]
}

例题

131. 分割回文串

剑指 Offer II 086. 分割回文子字符串

给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。 回文串 是正着读和反着读都一样的字符串。

答案

回溯递归 + 记忆化递归

• 回溯递归求字串
• 记忆化递归判断是否回文

var partition = function(s) {
  const n = s.length, ar = [], r = []
  const d = start => {
    if (start === n) return r.push(ar.slice())
    for (let i = start; i < n; i++) {
      if (isPalindrome(start, i) !== 1) continue 
      ar.push(s.substring(start, i + 1))
      d(i + 1)
      ar.pop()
    }
  }
  const h = Array.from({length : n}, _ => new Int8Array(n))
  const isPalindrome = (i, j) => {
    if (h[i][j] !== 0) return h[i][j]
    if (i >= j) h[i][j] = 1
    else if (s[i] === s[j]) h[i][j] = isPalindrome(i + 1, j - 1)
    else h[i][j] = -1
    return h[i][j]
  }
  d(0)
  return r
};

func partition(s string) [][]string {
  n := len(s)
  var r [][]string
  var ar []string
  h := make([][]int, n)
  for i := range h {
    h[i] = make([]int, n)
  }
  var isPalindrome func(i int, j int) int
  isPalindrome = func(i int, j int) int {
    if h[i][j] != 0 {
      return h[i][j]
    }
    if i >= j {
      h[i][j] = 1
    } else if s[i] == s[j] {
      h[i][j] = isPalindrome(i + 1, j - 1)
    } else {
      h[i][j] = 0
    }
    return h[i][j]
  }
  var d func(start int) 
  d = func(start int) {
    if start == n {
      r = append(r, append([]string(nil), ar...))
    }
    for i := start; i < n; i++ {
      if isPalindrome(start, i) != 1 {
        continue
      }
      ar = append(ar, s[start : i + 1])
      d(i + 1)
      ar = ar[:len(ar) - 1]
    }
  }
  d(0)
  return r
}

回溯递归 + 动态规划

• 回溯递归求字串
• 动态规划判断是否回文

var partition = function(s) {
  const n = s.length, dp = Array.from({length: n}, _ => new Uint8Array(n).fill(1))
  for (let i = n; i--;) {
    for (let j = i + 1; j < n; j++) {
      dp[i][j] = s[i] === s[j] ? dp[i + 1][j - 1] : 0
    }
  }
  const ar = [], r = []
  const d = start => {
    if (start === n) return r.push(ar.slice())
    for (let i = start; i < n; i++) {
      if (dp[start][i] === 0) continue
      ar.push(s.substring(start, i + 1))
      d(i + 1)
      ar.pop()
    }
  }
  d(0)
  return r
};

func partition(s string) [][]string {
  n := len(s)
  dp := make([][]int, n)
  for i := range dp {
    dp[i] = make([]int, n)
    for j := range dp[i] {
      dp[i][j] = 1
    }
  }
  for i := n - 1; i >= 0; i-- {
    for j := i + 1; j < n; j++ {
      if s[i] == s[j] {
        dp[i][j] = dp[i + 1][j - 1]
      } else {
        dp[i][j] = 0
      }
    }
  }
  var r [][]string
  var ar []string
  var d func(start int)
  d = func(start int) {
    if start == n {
      r = append(r, append([]string(nil), ar...))
    }
    for i := start; i < n; i++ {
      if dp[start][i] != 1 {
        continue
      }
      ar = append(ar, s[start : i + 1])
      d(i + 1)
      ar = ar[:len(ar) - 1]
    }
  }
  d(0)
  return r
}

132. 分割回文串 II

剑指 Offer II 094. 最少回文分割

给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是回文。 返回符合要求的 最少分割次数 。

答案

动态规划

var minCut = function(s) {
  const n = s.length, dp = Array.from({length : n}, _ => new Uint8Array(n).fill(1))
  for (let i = n; i--;) {
    for (let j = i + 1; j < n; j++) {
      dp[i][j] = s[i] === s[j] ? dp[i + 1][j - 1] : 0
    }
  }
  const f = new Uint16Array(n).fill(2001)
  for (let i = 0; i < n; i++) {
    if (dp[0][i] === 1) {
      f[i] = 0
      continue
    }
    for (let j = 0; j < i; j++) {
      if (dp[j + 1][i] === 1) {
        f[i] = Math.min(f[i], f[j] + 1)
      } 
    }
  }
  return f[n - 1]
};

func minCut(s string) int {
  n := len(s)
  dp := make([][]int, n)
  for i := range dp {
    dp[i] = make([]int, n)
    for j := range dp[i] {
      dp[i][j] = 1
    }
  }
  for i := n - 1; i >= 0; i-- {
    for j := i + 1; j < n; j++ {
      if s[i] == s[j] {
        dp[i][j] = dp[i + 1][j - 1]
      } else {
        dp[i][j] = 0
      }
    }
  }
  f := make([]int, n)
  for i := range f {
    f[i] = 2001
  }
  for i := 0; i < n; i++ {
    if dp[0][i] == 1 {
      f[i] = 0
      continue
    }
    for j := 0; j < i; j++ {
      if dp[j + 1][i] == 1 {
        f[i] = min(f[i], f[j] + 1)
      }
    }
  }
  return f[n - 1]
}
func min(a int, b int) int {
  if a < b {
    return a
  }
  return b
}

1278. 分割回文串 III

给你一个由小写字母组成的字符串 s，和一个整数 k。 请你按下面的要求分割字符串： 首先，你可以将 s 中的部分字符修改为其他的小写英文字母。 接着，你需要把 s 分割成 k 个非空且不相交的子串，并且每个子串都是回文串。 请返回以这种方式分割字符串所需修改的最少字符数。

答案

动态规划

var palindromePartition = function(s, k) {
  const n = s.length, cost = Array.from({length : n}, _ => new Uint8Array(n))
  for (let i = n; i--;) {
    for (let j = i + 1; j < n; j++) {
      cost[i][j] = cost[i + 1][j - 1] + (s[i] === s[j] ? 0 : 1)
    }
  }
  const dp = Array.from({length : n}, _ => new Uint8Array(k).fill(101))
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < k; j++) {
      if (j === 0) {
        dp[i][j] = cost[0][i]
        continue
      }
      for (let m = 0; m < i; m++) {
        dp[i][j] = Math.min(dp[i][j], dp[m][j - 1] + cost[m + 1][i])
      }
    }
  }
  return dp[n - 1][k - 1]
};

func palindromePartition(s string, k int) int {
  n := len(s)
  cost := make([][]int, n)
  for i := range cost {
    cost[i] = make([]int, n)
  }
  for i := n - 1; i >= 0; i-- {
    for j := i + 1; j < n; j++ {
      if s[i] == s[j] {
        cost[i][j] = cost[i + 1][j - 1]
      } else {
        cost[i][j] = cost[i + 1][j - 1] + 1
      }
    }
  }
  dp := make([][]int, n)
  for i := range dp {
    dp[i] = make([]int, k)
    for j := range dp[i] {
      dp[i][j] = 101
    } 
  }
  for i := 0; i < n; i++ {
    for j := 0; j < k; j++ {
      if j == 0 {
        dp[i][j] = cost[0][i]
        continue
      }
      for m := 0; m < i; m++ {
        dp[i][j] = min(dp[i][j], dp[m][j - 1] + cost[m + 1][i])
      }
    }
  }
  return dp[n - 1][k - 1]
}
func min (a int, b int) int {
  if a < b {
    return a
  }
  return b
}