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];
}
};