Palindrome Partitioning II

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.

无耻一点的话，可以再问题一的基础上，找结果集中元素最少的，当然就是分割最少的，厚道一些就dp了。

开始觉得很简答，利用问题一中的 判断子串是否是回文串的函数，进行dp，但是果断超时了，看来是否为回文的信息还要记录，就添加个数组，来记录从i 到 j 的字串是否为回文。

class Solution {
public:
   /*
     dp[k] = min{ dp[k], dp[j - 1] + 1} if s[j...k] is palindrom, 0 <=j <= k - 1;
     dp[k] = dp[k - 1] + 1，otherwise.
   */
   int minCut(string s){
		vector<int> dp(s.size() + 1, 0x7f7f7f7f);
		/*
		bplin[i][i] = true, but it‘s useless for this problem.
		*/
		vector<vector<bool> > bpalin(s.size(), vector<bool>(s.size(), false));
		dp[0] = -1;
		for(int i = 0; i < s.size(); ++i)
		{
		    //we assume s[i] can‘t make palindrome with items before it.
			dp[i + 1] = dp[i] + 1;
			//check if s[i] can make palindrome with items before it.
			//if so, we change  dp[i + 1].
			for(int cur = i - 1; cur >= 0; --cur)
				if(s[i] == s[cur] && (i - cur <= 2 || bpalin[cur + 1][i - 1])){
					dp[i + 1] = min(dp[i + 1], dp[cur] + 1);
					bpalin[cur][i] = true;
				}
		   
		}
		return dp[s.size()];
	}
};

Palindrome Partitioning II

原文：http://blog.csdn.net/shiquxinkong/article/details/18716703