EEPW论坛

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",

Return1since the palindrome partitioning["aa","b"]could be produced using 1 cut.

计算字符串切割次数最小，转换成回文数

1. class Solution  

2. {  

3. public:  

4.     int minCut(string s)  

5.     {  

6.         int len = s.size();  

7.   

8.         //用于描述s.substr(k, j-k+1)是否能构成回文子串的矩阵  

9.         //flag[k][j]=true；能构成回文子串  

10.         vector<vector<bool>> flag(len, vector<bool>(len, false));  

11.   

12.         //用于记录最佳分割次数vector  

13.         //初始化状态下，长为i的子串的最佳分割次数：vec[i]=i-1;  

14.         vector<int> vec(len+1);  

15.         for (int i=0; i<len+1; i++)  

16.         {  

17.             vec[i] = i - 1;  

18.         }  

19.   

20.         //进入动态规划  

21.         for (int i=0; i<len; i++)  

22.         {  

23.             for (int j = 0; j <= i; j++)  

24.             {  

25.                 //s中s[j][i]构成的子串（substr(j, i-j+1)）能不能构成回文字符串  

26.                 if (s[i] == s[j] && (i - j < 2 || flag[j+1][i-1])==true)  

27.                 {  

28.                     flag[j][i] == true;  

29.   

30.                     //此时前i个字符串的最佳分割或者原分割次数v[i+1]  

31.                     vec[i + 1] = min(vec[i+1], vec[j]+1);  

32.                 }  

33.             }  

34.         }  

35.         return vec[len];  

36.     }  

37. };