leetcode打怪升级系列：回文分割 II（132）
public static int minCut(String s) {int len = s.length();int[][] F = new int[len][len];//定义二维数组表示状态转移方程for (int i = 0; i < len; i++) {F[i][i] = 0;}for (int k = 2; k <= len; k++) {//子串长度从2取到lenfor (int i = 0; i <= len - k; i++) {int min = Integer.MAX_VALUE;for (int j = i; j < i + k; j++) {//在k长度的子串中取最小值if (j == i) {int ss = i, ee = i + k - 1;if (s.charAt(ss) == s.charAt(ee)&& (ss + 1 == ee || F[ss + 1][ee - 1] == 0)) {//判断是否是回文串min = 0;break;}} else {if (F[i][j - 1] != 0) {continue;}min = Math.min(F[i][j - 1] + F[j][i + k - 1] + 1, min);}}F[i][i + k - 1] = min;}}return F[0][len - 1];}
?
? ? ?此算法的时间负责度可见为O（n3），所以只过了leetcode上该题的小数据，大数据一直有一个数据是TLE，所以下面我会给出一个时间复杂度为O（n2）的算法。
?
（时间太晚了，回宿舍了，明天继续）
