由于131题找出所有字符串的回文划分我用了DFS，所以这题我想当然地套用了131题的思路，只修改了几行代码就提交了，然而TLE了……看来算法的复杂度还是太高了，那么下一步就考虑DP算法了，思路并不复杂，在Discuss区看到一个很简洁的写法https://leetcode.com/problems/palindrome-partitioning-ii/discuss/42198/My-solution-does-not-need-a-table-for-palindrome-is-it-right-It-uses-only-O(n)-space.，代码如下：
class Solution {
public:
int minCut(string s) {
int n = s.size();
// number of cuts for the first k characters
vector<int> cut(n+1, 0);
for (int i = 0; i <= n; i++) cut[i] = i-1;
for (int i = 0; i < n; i++) {
// odd length palindrome
for (int j = 0; i-j >= 0 && i+j < n && s[i-j]==s[i+j] ; j++)
cut[i+j+1] = min(cut[i+j+1],1+cut[i-j]);
// even length palindrome
for (int j = 1; i-j+1 >= 0 && i+j < n && s[i-j+1] == s[i+j]; j++)
cut[i+j+1] = min(cut[i+j+1],1+cut[i-j+1]);
}
return cut[n];
}
};
