Question ：

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.

Anwser 1 ：

class Solution {
public:
    int minCut(string s) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if (s.size() < 2)
            return 0;
        int length = s.size();
        int *minSegs = new int[length+1];
        minSegs[0] = 0;
        minSegs[1] = 1;
        int **dp = new int*[2];
        dp[0] = new int[length+2];
        dp[1] = new int[length+2];
        dp[0][0] = dp[1][0] = 0;
        dp[0][1] = dp[1][1] = 1;
        dp[0][2] = -1;
        
        int cur = 0;
        int pre = 1;
        for (int i=1; i<s.size(); i++) {
            int cur = i % 2;
            int pre = (i +1) % 2;
            minSegs[i+1] = minSegs[i] + 1;
            int n = 1;
            for (int j=0; dp[pre][j] != -1; j++) {
                int left = i-1-dp[pre][j];
                if (left>=0 && s[left]==s[i]) {
                    dp[cur][++n] = dp[pre][j] + 2;
                    if (minSegs[left] + 1 < minSegs[i+1])
                        minSegs[i+1] = minSegs[left] + 1;
                }
            }
            dp[cur][++n] = -1;
        }
        
        int min = minSegs[s.size()] - 1;
        delete []minSegs;
        return min;
    }
};

Anwser 2: ：

class Solution {
public:
    int minCut(string s) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
		int len=s.length();
		int BIG=2*len;
		int num_line=len+1;
		vector<int> isPalindrome(num_line*num_line);
		for(int l=1;l<=len;l++)//两个木板之间有多少个字符
		{
			for (int i=0;i+l<num_line;i++)//从第0个木板开始,i+l为木板的序号
			{
				if (l==1)
				{
					isPalindrome[i*num_line+(i+l)]=1;
				}
				else if(l==2)
				{
					if (s[i]==s[i+l-1])
						isPalindrome[i*num_line+(i+l)]=1;
					else
						isPalindrome[i*num_line+(i+l)]=BIG;
				}
				else
				{
					if (s[i]==s[i+l-1])
						isPalindrome[i*num_line+(i+l)]=isPalindrome[(i+1)*num_line+(i+l-1)];
					else
						isPalindrome[i*num_line+(i+l)]=BIG;
				}
			}
		}
		vector<int> dist(num_line);
		vector<bool> labeled(num_line);
		for(int i=0;i<num_line;i++)
		{
			dist[i]=BIG;
			labeled[i]=false;
		}
		dist[0]=0;
		labeled[0]=true;
		int current_line=0;
		for(int i=1;i<num_line;i++)
		{	
			for(int d=current_line+1;d<num_line;d++)//对所有的相邻（在图中）的木板
			{
				if(!labeled[d])
				{
					if (dist[current_line]+isPalindrome[current_line*num_line+d]<dist[d])
					{
						dist[d]=dist[current_line]+isPalindrome[current_line*num_line+d];
					}
				}
			}
			int mindist=BIG;
			int minindex=-1;
			for(int i=0;i<num_line;i++)
			{
				if(!labeled[i])
				{
					if(mindist>dist[i])
					{
						minindex=i;
						mindist=dist[i];
					}
				}
			}
			current_line=minindex;
			labeled[minindex]=true;
		}

		return dist[num_line-1]-1;
	}
};

参考推荐：

leetcode:Palindrome Partitioning II