leecode 解题总结：132. Palindrome Partitioning II

#include <iostream>#include <stdio.h>#include <vector>#include <string>using namespace std;/*问题: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.分析：仍然可以采用回溯方法，设定一个计数器变量。对字符串s[0...n-1]遍历每个i从0~n-1,来划分字符串为s[0...i],s[i+1..n-1]，如果当前划分后字符串的左侧是回文的，将左边部分压入结果，并令划分次数加1并对字符串的右边部分进行递归，当递归结束后，结果中存放了一个划分，此时回溯，弹出当前字符串的左边部分，并令划分次数减一。如果字符串的划分走到了末尾，就将划分结果存入结果集，并比较划分次数和已经记录的最小划分次数。输入:aabaabbabcdaababab输出:12302报错:超时，当输入这个的时候"ababababababababababababcbabababababababababababa"因此，应该还有例如dp等方法来做。假设字符串为A[1..n]分析，设dp[i]表示字符串A[1...i]的最小划分次数，那么dp[i+1]与dp[i]的关系是什么?,比如以aabb举例，dp[1]=0,1个字符无需划分dp[2]=0,无需划分，因为A[1..i]本身是回文dp[3]=1,因为A[1..3]不是回文，但A[1..2]是回文，所以只需要切分出最小回文的下标出，分成两部分即可发现dp[i+1]={0,if A[1...i+1]是回文的            {dp[i] + 1, else 如果A=abadp[1]=0dp[2]=1dp[3]=0ababab设dp[i]表示字符串A[0...i]的最小划分次数所以总结的状态迁移方程为dp[i+1]={0,     if A[0...i+1] 是回文      {min{dp[j]}+1, j属于[0,i] ,else dp[0]=0所求目标是dp[n-1]这个规划有问题不如设dp[i][j]表示字符串A[i..j]的最小划分次数，设dfs(s,beg,end)能求出最小划分次数dfs(s,0,0)=0=dp[0]dfs(s,i,j)={0,if A[i...j]回文           {		   i <= k < j		   if( dfs(s,i,k) )//回文				 result = min{ result , dfs(s,i,k) + dfs(s,k+1,j)}leecode解法:https://discuss.leetcode.com/topic/2048/my-dp-solution-explanation-and-code/4采用动态规划设定一个数组pal[i][j]表示s[i..j]是否是回文字符串设d[i]表示s[i...n-1]的最小划分次数。那么从后向前遍历，如果s[i] == s[j] && (j - i < 2 || pal[i+1][j-1])即两边字符相等，中间部分又是回文的,更新pal[i][j]=true，说明其实整个s[i...j]是回文的，剩余s[j+1...n-1]的最小次数为d[j+1],总的划分次数为先划分s[i...j](肯定回文，划分占据一次),总的划分次数s[i..n-1]=min(d[i] , 1 + d[j+1])牛逼。所求结果为d[0]*/class Solution {public:	int minCut(string s) {		if(s.empty())		{			return 0;		}		int len = s.length();		vector< vector<bool> > pal( len , vector<bool>(len , false) );		vector<int> dp(len , 0);		//从后向前遍历，因为求dp[i]依赖于于前面的dp[i+1],dp[i+2],...,dp[n-1]		for(int i = len -1 ; i >= 0 ; i--)		{			dp.at(i) = len - 1 - i;			for(int j = i ; j < len; j++)			{				//如果s[i...j]是回文串，开始计算s[i...n-1]的最小划分次数				if(s[i] == s[j] && (j - i < 2 || pal[i+1][j-1]))				{					//需要设定当前pal[i][j]为true					pal[i][j] = true;					//如果s[i...n-1]是回文串，那么dp[i] = 0					if(j == len-1)					{						dp[i] = 0;					}					else					{						//s[i...n-1]最小划分次数=先划分为s[i...j]的次数1次 + s[j+1...n-1]的划分次数dp[j+1] ,j 必须小于n						dp.at(i) = min( dp.at(i) , dp.at(j+1) + 1 );					}				}			}		}		return dp.at(0);	}};void process(){	 string value;	 int num;	 Solution solution;	 vector<int> result;	 while(cin >> value )	 {		 num = solution.minCut(value);		 cout << num << endl;	 }}int main(int argc , char* argv[]){	process();	getchar();	return 0;}/*	bool isPalindrome(int begin , int end , string& s)	{		if(s.empty())		{			return true;		}		if(begin < 0 || end >= s.length() || begin > end)		{			return false;		}		int low = begin;		int high = end;		bool isOk = true;		while(low < high)		{			if(s.at(low) != s.at(high))			{				isOk = false;				break;			}			low++;			high--;		}		return isOk;	}	void backTrace(int begin , string& s , int& cutTimes, int& minTimes)	{		if(begin < 0 || s.empty())		{			return;		}		//已经计算出一次完整的划分，比较		if(begin == s.length())		{			minTimes = min(minTimes , cutTimes);			return;		}		int len = s.length();		for(int i = begin ; i < len ; i++)		{			//如果左边是回文串，对右边进行递归处理			if(isPalindrome(begin , i , s))			{				cutTimes++;				backTrace(i + 1 , s , cutTimes , minTimes);				//回溯，需要重新设置次数为原始值				cutTimes--;			}		}	}    int minCut2(string s) {        int minTimes = INT_MAX;		//之所以不是0，是因为如果一开始就是回文串，那么在回溯的时候会因为判断是回文串，累加一次，变为0,否则，初始为0，累加1次变成1，就不对了		int cutTimes = -1;		backTrace(0 , s , cutTimes , minTimes);		return minTimes;    }*/