#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;    }*/