题目

Given a string s, partition s such that every substring of the partition is a palindrome.

Return the minimum cuts needed for a palindrome partitioning of s.

For example, given s = “aab”,
Return 1 since the palindrome partitioning [“aa”,”b”] could be produced using 1 cut.

思路

此题可以用动态规划求解。isPal[j][i]表示字符串s的子串s[j…i]是否为回文串，cut[i]表示子串s[0…i]所需要的最小分割数

代码

    /**------------------------------------
    *   日期：2015-03-02
    *   作者：SJF0115
    *   题目: 132.Palindrome Partitioning II
    *   网址：https://oj.leetcode.com/problems/palindrome-partitioning-ii/
    *   结果：AC
    *   来源：LeetCode
    *   博客：
    ---------------------------------------**/
    #include 
   
     #include 
    
      #include 
     
       #include 
      
        using namespace std; class Solution { public: int minCut(string s) { int size = s.size(); if(size == 0){ return 0; }//if // isPal[i][j]表示字符串s的子串s[i,j]是否为回文串 bool isPal[size][size]; memset(isPal,0,sizeof(isPal)); // cut[j]表示子串s[0,j]所需要的最小分割数 int cut[size]; // cut[0,i] for(int i = 0;i < size;++i){ // [0,i]最多分割i次 cut[i] = i; // 判断s[j,i]是否是回文串 for(int j = 0;j <= i;++j){ // s[j,i]是回文串 if(s[j] == s[i] && (i - j <= 1 || isPal[j+1][i-1])){ isPal[j][i] = true; // s[0,i]是回文串 if(j == 0){ cut[i] = 0; }//if else{ cut[i] = min(cut[i],cut[j-1]+1); }//else }//if }//for }//for return cut[size-1]; } }; int main(){ Solution s; string str("cabababcbc"); cout<