回文划分 – SweetCigarettes

Problem

对于一个给定的字符串s(|S| < 5000)，求最少能分割成多少个回文串。
例如，字符串ababbab可以划分成[a][babbab]。

动态规划，$opt[i]$表示从字符串前i位的最小划分分出的子串数量，那么转移方程是——当子串$[j,i]$是回文的时候$opt[i] = min\{ opt[i], opt[j -1] + 1\}$。
如果用暴力的方法判断一个子串是否是回文串，再用动态规划来更新，算法的渐进时间复杂度是$O(|S|^3)$，会超时。所以我们需要用到回文串的对称性质寻找回文，更新$opt[1…|S|]$数组。

#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;

}

浏览量: 519