题目

题目来源：力扣（LeetCode）

给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是回文。

返回符合要求的 最少分割次数 。

示例 1：

输入：s = “aab”
输出：1
解释：只需一次分割就可将 s 分割成 [“aa”,”b”] 这样两个回文子串。

示例 2：

输入：s = “a”
输出：0

示例 3：

输入：s = “ab”
输出：1

思路分析

使用两次动态规划解决这道问题。

第一次 dp 使用二维数组判断 区间范围[i, j] 的子串是否是回文字符串
第二次 dp 根据第一次 dp 的预处理结果求取 范围是[0, i]的回文子串的最少分割次数

  1. /**
  2.  * @param {string} s
  3.  * @return {number}
  4.  */
  5. var minCut = function (s) {
  6.   const n = s.length;
  7.   const g = new Array(n).fill(0).map(() => new Array(n).fill(true));
  8.   // 第一次动态规划 数据预处理 求出字符串 所有子串是否为回文串 true/false
  9.   // g[i][j] 代表 [i, j] 这一段是否为回文
  10.   // g[i][j] 是否回文，必须满足以下两个条件：
  11.   // g[i+1][j−1]=true
  12.   // s[i] == s[j]
  13.   // g[i][j] 是否回文，是依赖于 g[i+1][j−1] 的，只有 g[i+1][j−1] 为true时，才能赋值 g[i][j] 为true
  14.   // 在 g[i][j] 二维数组中，g[i+1][j−1]是在 g[i][j] 的左下角的
  15.   // 为了保证 g[i + 1][j - 1]都是经过计算的，一定要先从下到上遍历行，然后从左到右遍历遍历列
  16.   for (let i = n - 1; i >= 0; --i) {
  17.     for (let j = i + 1; j < n; ++j) {
  18.       g[i][j] = s[i] == s[j] && g[i + 1][j - 1];
  19.     }
  20.   }
  22.   const dp = new Array(n).fill(Number.MAX_SAFE_INTEGER);
  23.   // 第二次动态规划  dp[i]为 0 ~ i分割回文串的最小分割次数
  24.   // 如果 0 ~ i 本身为回文串 则分割次数为0
  25.   for (let i = 0; i < n; ++i) {
  26.     if (g[0][i]) {
  27.       dp[i] = 0;
  28.     } else {
  29.       for (let j = 0; j < i; ++j) {
  30.         // 如果j + 1 到 i 是回文串
  31.         if (g[j + 1][i]) {
  32.           dp[i] = Math.min(dp[i], dp[j] + 1);
  33.         }
  34.       }
  35.     }
  36.   }
  38.   return dp[n - 1];
  39. };

参考阅读： https://leetcode-cn.com/problems/palindromic-substrings/solution/dai-ma-sui-xiang-lu-dai-ni-xue-tou-dpzi-vidge/ https://leetcode-cn.com/problems/palindrome-partitioning-ii/solution/132-fen-ge-hui-wen-chuan-iidong-tai-gui-3hqva/ https://leetcode-cn.com/problems/palindrome-partitioning-ii/solution/dong-tai-gui-hua-by-liweiwei1419-2/