Java剑指 Offer II 094. 最少回文分割（击败53.39%用户）

题目：
给定一个字符串 s，请将 s 分割成一些子串，使每个子串都是回文串。
返回符合要求的 最少分割次数 。

示例 :
输入：s = "aab"
输出：1
解释：只需一次分割就可将 s 分割成 ["aa","b"] 这样两个回文子串。
思路：
如果要求列出切割的各个方案就适合用回溯法，之前写过。
现在只要求给出最少次数，用动态规划合适。
找状态转移方程： dp[i] = Math.min(dp[i],dp[j-1]+1);

复杂度：
时间：双重循环O（n*n）。
空间：isPal【】【】二维数组空间O（n^2）。

代码：效率比较拉胯，但是比较容易懂
public int minCut(String s) {
int n = s.length();
boolean[][] isPal = new boolean[n][n];
//判断s从下标j到i是否回文
for(int i = 0;i

Java剑指 Offer II 094. 最少回文分割（击败53.39%用户）最先出现在Python成神之路。