P3995.回文字符串分割
题面描述
给定一个只包含小写字母的字符串 s（长度为 n）和一个整数 k。请将 s 切分成恰好 k 个非空且连续的子串，并使得每个子串都是回文串。求满足条件的切分方案数；若无解则输出 0。
切分的位置不同视为不同方案。
输入输出
输入：
第一行一个字符串 s。
第二行一个整数 k。
输出：
输出一个整数，表示将 s 切分成 k 个回文子串的方案数。
数据范围
- 1≤n=∣s∣≤60
- 1≤k≤n
- 字符仅由小写字母组成
样例
输入
aab
2
输出
1
说明
只存在切分 aa|b。
输入
aaaa
3
输出
3
说明
可行切分为 a|a|aa、a|aa|a、aa|a|a。
开通会员即可查看完整视频题解： 1.题目讲解 2.思路分析 3.逐行代码手写
