给定一个字符串 s，将 s 分割成一些子串，使每个子串都是回文串。
返回符合要求的最少分割次数。
示例:
输入: "aab"
输出: 1
解释: 进行一次分割就可将 s 分割成 ["aa","b"] 这样两个回文子串
与131题目类似，但是用递归的话在某些测例上会超时，因此考虑使用dp
使用dp,首先考虑回文的特点，从头与从尾开始，对应点的字符相等。
对一个i~j的字符串，如果我们已经判断完i+1~j-1是否为回文了，就不用重新一个个对应判断了。只要s[i]==s[j]且i+1~j-1是回文串，就可以直接判断它为回文。
因此：
状态定义:table[i][j]----->从i到j的子串是否为回文串
状态转移:
1).s[i]!=s[j]---->table[i][j]=0。i~j非回文
2).s[i]==s[j]:
a).j-i<=1，即i和j重合或相邻，此时为回文串。
b).table[i+1][j-1]如果为回文，则table[i][j]=1，否则非回文。
以上状态转移方程即可解得回文串的整个分布。
同时，题目要求的是解出最小分割次数。
在求解i~n-1中间的回文串状态时可以同时求出它的最小分割情况。
定义另外一个状态转移方程:
状态定义:dp[i]---->i~n-1中最小分割次数
状态转移方程:
1)i==n-1:在最后，此时应该为0
2)i!=n-1:dp[i]=min(dp[i],1+dp[j+1])---->i~j为回文串，i~n-1的最小分割次数应该是到j分割一次后，加上dp[j+1]（也就是j+1~n-1的最小分割次数）。再通过一个min来选择其中最小的分割方案。
class Solution {
public:
int minCut(string s) {
vector<vector<int>> table(s.size(),vector<int>(s.size(),0));
vector<int> dp(s.size());
for(int i=s.size()-1;i>=0;i--)//aabaa
{
dp[i]=INT_MAX;
for(int j=i;j<s.size();j++)
{
if(s[i]==s[j]&&((j-i<=1)||(table[i+1][j-1]==1)))
{
table[i][j]=1;
if(j==s.size()-1)
dp[i]=0;
else
{
dp[i]=min(dp[i],1+dp[j+1]);
}
}
}
}
return dp[0];
}
};