Problem
对于一个给定的字符串s(|S| < 5000),求最少能分割成多少个回文串。
例如,字符串ababbab可以划分成[a][babbab]。
Solution
- 动态规划,$opt[i]$表示从字符串前i位的最小划分分出的子串数量,那么转移方程是——当子串$[j,i]$是回文的时候$opt[i] = min\{ opt[i], opt[j -1] + 1\}$。
- 如果用暴力的方法判断一个子串是否是回文串,再用动态规划来更新,算法的渐进时间复杂度是$O(|S|^3)$,会超时。所以我们需要用到回文串的对称性质寻找回文,更新$opt[1…|S|]$数组。
Code
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |
#include <iostream> #include <string> using namespace std; string str; int opt[5000 + 5]; int main() { ios::sync_with_stdio(false); cin >> str; int len = str.size(); str = " " + str; for (int i = 1; i <= len; ++i) { opt[i] = opt[i - 1] + 1; } for (int i = 1; i <= len; ++i) { int j = 0; while (i - j >= 1 && i + j <= len && str[i - j] == str[i + j]) { opt[i + j] = min(opt[i - j - 1] + 1, opt[i + j]); ++j; } j = 0; while (i - j >= 1 && i + j + 1 <= len && str[i - j] == str[i + j + 1]) { opt[i + j + 1] = min(opt[i + j + 1], opt[i - j - 1] + 1); ++j; } } cout << opt[len] << endl; return 0; } |
说点什么