【3.8】LeetCode每日一题· 分割回文串 II

2021年03月08日 10时50分

标签： LeetCode 动态规划

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

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

#### 示例2
	输入：s = "a"
	输出：0

#### 示例3
	输入：s = "ab"
	输出：1

#### 提示
	1 <= s.length <= 2000
	s 仅由小写英文字母组成

#### 来源
> 来源：力扣（LeetCode）
> 链接：[题目链接](https://leetcode-cn.com/problems/palindrome-partitioning-ii/ "题目链接")

## 解题思路
一开始考虑到贪心，从左往右每次都取最长的回文串分割，但是有反例

"aaaaba"
	最优解：["aaa", "aba"]
	贪心：["aaaa", "b", "a"]

因此贪心失败。
由于问题具有**最优子结构**的性质，考虑动态规划。

设`dp[i] := s[0..i]的满足条件的最小分割次数`，考虑在`s[0..i]`中间任意位置分隔一次，形成左右两个子串（在首或尾部进行分割相当于不分割），那么会有如下状态转移方程
	如果s[0..i]是回文串，则
		dp[i] = 0
	如果s[0..i]不是回文串，则
		dp[i] = min{ dp[k]+1 | s[k+1..i]是回文串, 0<=k<i }
那么问题就转化为如何判断`s[i..j]`是否为回文串，可以考虑[【3.7】每日一题](http://www.vison307.com/27/ "【3.7】每日一题")，采用另一个dp求解。

求回文串预处理的dp时间复杂度为$$O(N^2)$$，判断子串是否为回文串的时间复杂度为$$O(1)$$，因此总的时间复杂度为$$O(N^2)$$。
空间复杂度：$$O(N^2)$$

## 代码
	class Solution {
	public:
		int minCut(string s) {
			const int N = s.length();
			vector<vector<bool>> f(N, vector<bool>(N, true));
			f[0][0] = true;
			for(int i = N-1; i >= 0; --i){
				for(int j = i+1; j < N; j++){
					f[i][j] = (f[i+1][j-1] && s[i] == s[j]);
				}
			}
			vector<int> dp(N, INT_MAX);
			dp[0] = 0;
			for(int i = 1; i < N; i++){
				if(f[0][i]){
					dp[i] = 0;
				}else{
					for(int j = 0; j < i; j++){
						if(f[j+1][i]){
							dp[i] = min(dp[i], dp[j]+1);
						}
					}
				}
			}
			return dp[N-1];
		}
	};

## 用时和内存
> 执行用时：32 ms，在所有 C\++提交中击败了72.57%的用户
> 内存消耗：7 MB，在所有 C\++提交中击败了79.91%的用户

所有评论

暂无评论

新增评论

邮箱

邮箱仅作验证使用

图形验证码

邮箱验证码

目录

【3.8】LeetCode每日一题· 分割回文串 II

所有评论

暂无评论

新增评论