给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是回文。
返回符合要求的 最少分割次数 。
示例 1：
输入：s = "aab"
输出：1
解释：只需一次分割就可将 s 分割成 ["aa","b"] 这样两个回文子串。
> 动态规划
class Solution {
public:
int minCut(string s) {
vector<vector<int>> dp(s.size(),vector<int>(s.size(),1));
for(int i = s.size()-1;i >= 0;i--){
for(int j = s.size()-1;j > i;j--){
if(s[i] == s[j]){
dp[i][j] = dp[i+1][j-1];
}
else{
dp[i][j] = 0;
}
}
}
int n = s.size();
vector<int> f(n);
for(int j = 1; j < n; j++) {
if(dp[0][j])
f[j] = 0;
else {
f[j] = f[j-1] + 1;
for(int i = 1; i < j; i++) {
if(dp[i][j])
f[j] = min(f[j], f[i-1] + 1);
}
}
}
return f[n-1];
}
};