回文划分

Problem

对于一个给定的字符串s(|S| < 5000),求最少能分割成多少个回文串。

例如,字符串ababbab可以划分成[a][babbab]。

Solution

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

Code

 

说点什么

avatar
50
  Subscribe  
提醒