点我(^_^)
题目大意返回最少地将字符串s分隔成全是回文子串的次数
解题思路其实很容易就能想到，如果 dp[i] 表示将 s[0]~s[i]分隔成全是回文子串的最少次数，那么就会有如下状态转移方程。
这样做的时间复杂度是 O(n^2)*(每次判断是否为回文串的时间)，所以我们只要能 O(1) 判断是否为回文串，这题就迎刃而解了，如果是 O(1)，那就必然是要预处理。我们可以这样想，如果 s[i+1]...s[j-1] 已经为回文串了，那么如果 s[i]==s[j]，那么此时 s[i]...s[j] 也为回文串，这样的话长的字符串由短的字符串转移，可以使用动态规划，我们用 check[i][j] 表示 s[i]...s[j] 是否为回文串，那么可以得到如下转移方程。
需要注意的是，我们第一层循环要枚举长度，因为只有所有短的都已知，才能正确判断长的。
class Solution {
public:
int minCut(string s) {
vector> check(s.size(),vector(s.size(),true));
for(int len=2; len<=s.size(); ++len)
for(int i=0; i= s.size())
break;
check[i][j] = check[i+1][j-1] && (s[i]==s[j]);
}
vector dp(s.size(), 2005);
for(int i=0; i 
