专栏：50多种数据结构彻底征服

专栏：50多种经典图论算法全部掌握

昨天华为发文称：华为2026届实习生招聘计划正式启动，主要面向的是海内外高校学生，提供的实习岗位有研发类，销售类等，工作地点包括深圳、北京、上海、杭州、南京、武汉、西安、成都、东莞、苏州等地。

官方没有具体公布招聘的人群要求，只提到了“高校”两个字，网上查了一下没有“高校”这个词，只有高等学校，而高等学校包含普通高等学校，职业高等学校，成人高等学校，但结合以往华为招聘信息来看，本次招聘应该是高校本科生起步。如果有需要的可以点击下面的原文链接去注册简历投递。

--------------下面是今天的算法题--------------

来看下今天的算法题，这题是LeetCode的第132：分割回文串 II。

问题描述

来源：LeetCode第132题

难度：困难

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

示例1：

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

示例2：

输入：s = "a" 输出：0

  • 1 <= s.length <= 2000

  • s 仅由小写英文字母组成

问题分析

这题让把字符串分割成一些子串，并且每个子串都是回文串，求最小分割次数。之前我们讲过 ，之前那道题让返回的是所有可能的分割方案，而这题让求的是最小分割次数。

这题我们可以使用动态规划来解决，定义dp[i]表示前 i 个字符的最小分割次数。

1，如果前 i 个字符构成的子串s[0,i]是回文串，则不需要分割，也就是dp[i]=0。

2，否则就尝试分割，从前 i 个字符中不断截取子串s[j,i]，判断子串s[j,i]是否是回文串，如果是回文串，表示子串s[j,i]可以单独分割，然后前面分割的最少次数就是dp[j-1]，这里要枚举 j ，求最小的dp[i]，所以dp[i]=min(dp[i],dp[j-1]+1); 。

为了快速判断一个子串是否是回文串，我们需要先对所有的子串进行预处理，提前知道哪些是回文的，哪些不是。

JAVA：

public int minCut(String s) {     int length = s.length();     int[] dp = newint[length];     // 判断子串[i…j]是否是回文串     boolean[][] palindrome = newboolean[length][length];     for (int j = 0; j < length; j++) {         for (int i = 0; i <= j; i++) {             // 如果子串s[j,i]是回文串，则两边的字符s[i]和s[j]必须相同，并且             // 中间的子串s[i+1,j-1]如果存在，也必须是回文串。             if (s.charAt(i) == s.charAt(j) && (j - i <= 2 || palindrome[i + 1][j - 1]))                 palindrome[i][j] = true;         }     }     // 字符串s的回文子串最大也只能是字符串的长度，这里都默认初始化为最大值。     Arrays.fill(dp, length);     for (int i = 0; i < length; i++) {         // 如果子串s[0,i]本身就是回文的，就不需要分隔。         if (palindrome[0][i]) {             dp[i] = 0;         } else {             // 否则就要分隔，找出最小的分隔方案             for (int j = 0; j <= i; ++j) {                 if (palindrome[j][i])                     dp[i] = Math.min(dp[i], dp[j - 1] + 1);             }         }     }     return dp[length - 1]; }

C++：

public:     int minCut(string s) {         int length = s.length();         // 判断子串[i…j]是否是回文串         vector

 > palindrome(length, vector

 (length, false));         for (int j = 0; j < length; j++) {             for (int i = 0; i <= j; i++) {                 // 如果子串s[j,i]是回文串，则两边的字符s[i]和s[j]必须相同，并且                 // 中间的子串s[i+1,j-1]如果存在，也必须是回文串。                 if (s[i] == s[j] && (j - i <= 2 || palindrome[i + 1][j - 1]))                     palindrome[i][j] = true;             }         }         // 字符串s的回文子串最大也只能是字符串的长度，这里都默认初始化为最大值。         vector

  dp(length, length);         for (int i = 0; i < length; i++) {             // 如果子串s[0,i]本身就是回文的，就不需要分隔。             if (palindrome[0][i]) {                 dp[i] = 0;             } else {                 // 否则就要分隔，找出最小的分隔方案                 for (int j = 0; j <= i; ++j) {                     if (palindrome[j][i])                         dp[i] = min(dp[i], dp[j - 1] + 1);                 }             }         }         return dp[length - 1];     }

笔者简介

博哥，真名：王一博，毕业十多年， 作者，专注于 数据结构和算法 的讲解，在全球30多个算法网站中累计做题2000多道，在公众号中写算法题解800多题，对算法题有自己独特的解题思路和解题技巧，喜欢的可以给个关注，也可以 下载我整理的1000多页的PDF算法文档 。