Description

[Leetcode 132]

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

Input Format

第一行输入字符串长度n，第二行输入字符串。（1 <= n <= 2000）

Output Format

输出符合要求的最少分割次数。

3
aab​

1​

Hint

对样例的解释：

进行一次分割就可将 s 分割成 ["aa","b"] 这样两个回文子串

Source

动态规划 基础百练