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[i][j]=min(dp[i][k]+dp[k+1][j]+1), i<=k<j.
但是用这个方程的时间是O(n^3),简化dp[i][j]为dp[i],表示从0到i的minCut.
dp[i]=min(dp[k]+1(s[k+1, i]是回文串, dp[k]+i-k(s[k+1, i]不是回文串)), 0<=k<i.
这个方法在BOJ上过了,但是在leetcode上面 Judge Large 还是超时。。。
还没找到更快的方法。。。路过的人帮解一下吧。。。
class Solution {
public:
    
bool IsPalindrome(string s, int i, int j){
        
if(i==j)
            
return true;
        
while(i<j){
            
if(s[i++]!=s[j--])
                
return false;
        }
        
return true;
    }
    
int minCut(string s) {
        
// Start typing your C/C++ solution below
        
// DO NOT write int main() function
        int n = s.length();
        
if(n==0 || n==1)    
            
return 0;
        vector
<int> min;
        
for(int i=0; i<n; i++)
            min.push_back(
0);
        
int tmp, ans;
        
for(int inter=1; inter<n; inter++){
            
if(IsPalindrome(s, 0, inter)){
                min[inter]
=0;
            }
            
else{
                ans 
= n+1;
                
for(int k=0; k<inter; k++){
                    
if(IsPalindrome(s, k+1, inter))
                        tmp 
= min[k]+1;
                    
else
                        tmp 
= min[k]+inter-k;
                    
if(tmp<ans)
                        ans 
= tmp;
                }
                min[inter]
=ans;
            }
        }
        
return min[n-1];   
    }
};

经高人hadn't指点,超时是因为判断回文串太慢,加上记忆化数组判断回文串就pass了^-^
class Solution {
public:
    vector
< vector<int> > map;
    
int IsPalindrome(string &s, int i, int j){
        
if(i>j) return false;
        
if(map[i][j]!=-1)
            
return map[i][j];
        
if(i==j){
            
return map[i][j] = 1;
        }
            
        
if(s[i]!=s[j])
            
return map[i][j] = 0;
        
else{
            
if(j-i==1)
                
return map[i][j] = 1;
            
else
                
return map[i][j] = IsPalindrome(s, i+1, j-1);
        }
            
        
    }
    
int minCut(string s) {
        
// Start typing your C/C++ solution below
        
// DO NOT write int main() function
        int n = s.length();
        
if(n==0 || n==1)    
            
return 0;
        vector
<int> min, vtmp;
        
        min.clear(); vtmp.clear(); map.clear();
        
for(int i=0; i<n; i++){
            min.push_back(
0);
            vtmp.push_back(
-1);
        }
        
for(int i=0; i<n; i++)
            map.push_back(vtmp);
            
        
int tmp, ans;
        
for(int inter=1; inter<n; inter++){
            
if(IsPalindrome(s, 0, inter)){
                min[inter]
=0;
            }
            
else{
                ans 
= n+1;
                
for(int k=0; k<inter; k++){
                    
if(IsPalindrome(s, k+1, inter))
                        tmp 
= min[k]+1;
                    
else
                        tmp 
= min[k]+inter-k;
                    
if(tmp<ans)
                        ans 
= tmp;
                }
                min[inter]
=ans;
            }
        }
        
return min[n-1];   
    }
};