开始使用搜索，TLE:

class Solution {
public:
    int ans;
    int minCut(string s) {
        ans = 0xffffff;
        if(s.length() <= 0)return ans;
        bool *flag = new bool[s.length()+1];
        for(int i = 0;i <= s.length();i++)
            flag[i] = false;
        flag[0] = true;
        PartitionStep(s,1,flag);
        return ans;
    }
private:
    void PartitionStep(string s,int step,bool *flag) {
        if(step == s.length()) {
            int i;
            flag[step] = true;
            for(i = step-1;i >= 0;i--) {
                if(flag[i] == true)break;
            }
            if(IsPalindrome(s,i,step-1)) {
                int count = 0;
                for(int i = 0;i <=step;i++) {
                    if(flag[i] == true)count++;
                }
                if(count-2 < ans)ans = count-2;
            }
            flag[step] =false;
            return ;
        }
        flag[step] = true;
        int i;
        for(i = step-1;i >= 0;i--) {
            if(flag[i] == true)break;
        }
        if(IsPalindrome(s,i,step-1)) {
            PartitionStep(s,step+1,flag);
        }
        flag[step] = false;
        PartitionStep(s,step+1,flag);
    }
    bool IsPalindrome(string s,int i,int j) {
        while(i < j) {
            if(s[i] != s[j])return false;
            i++;
            j--;
        }
        return true;
    }
};

后来使用DP，惭愧研究了别人的思想：
http://blog.csdn.net/doc_sgl/article/details/13418125

class Solution {
public:
    int minCut(string s) {
        int lens = s.length();
        bool **isP;
        isP = new bool *[lens];
        for(int i = 0;i < lens;i++) {
            isP[i] = new bool [lens];
            for(int j = 0;j < lens;j++) {
                isP[i][j]  = false;
            }
        }
        for(int i = 0;i < lens;i++)
            isP[i][i] = true;</p>

<pre><code>    int * dp = new int[lens+1];
    for(int i = lens;i &amp;gt;= 0;i--)
        dp[i] = lens - 1 - i;
    for(int i = lens-1;i &amp;gt;= 0;i--) {
        for(int j = i;j &amp;lt; lens;j++) {
            if(((j - i) &amp;lt;= 2 || isP[i+1][j-1]) &amp;amp;&amp;amp; s[i] == s[j]) {
                isP[i][j] = true;
                dp[i] = dp[i] &amp;gt; dp[j+1]+1?dp[j+1]+1:dp[i];
            }
        }
    }
    return dp[0];
}
</code></pre>

<p>};