大家好，我是小魔龙，Unity3D软件工程师，VR、AR，虚拟仿真方向，不定时更新软件开发技巧，生活感悟，觉得有用记得一键三连哦。
一、题目
1、算法题目
“给定一个字符串，将字符串分割成一些子串，使每个子串都是回文串，返回符合要求的最少分割次数。”
2、题目描述
给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是回文。
返回符合要求的 最少分割次数 。
示例 1： 输入： s = "aab" 输出： 1 解释： 只需一次分割就可将 s 分割成 ["aa","b"] 这样两个回文子串。
示例 2： 输入： s = "a" 输出： 0
二、解题
1、思路分析
这道题是一道常规的动态规划提，首先定义f[r]为将[1,r]这一段字符分割成若干回文串的最小分割次数，那么答案就是f[n]。
那么就可以考虑f[r]是如何进行转移的：
- 从起点开始到第r个字符，能形成回文串，最小分割次数为0，此时f[r]=0
- 从起点开始到第r个字符，不能形成回文串，那么如果[l,r]这一段是回文串的话，那么就有f[r]=f[l-1]+1
枚举左端点，找出所有满足回文要求的左端点，在方案中选最小的一个即可。
2、代码实现
代码参考：
class Solution { public int minCut(String s) { int n = s.length(); boolean[][] g = new boolean[n][n]; for (int i = 0; i < n; ++i) { Arrays.fill(g[i], true); } for (int i = n - 1; i >= 0; --i) { for (int j = i + 1; j < n; ++j) { g[i][j] = s.charAt(i) == s.charAt(j) && g[i + 1][j - 1]; } } int[] f = new int[n]; Arrays.fill(f, Integer.MAX_VALUE); for (int i = 0; i < n; ++i) { if (g[0][i]) { f[i] = 0; } else { for (int j = 0; j < i; ++j) { if (g[j + 1][i]) { f[i] = Math.min(f[i], f[j] + 1); } } } } return f[n - 1]; } }
3、时间复杂度
时间复杂度：O(n2)
其中n是字符串s的长度。
空间复杂度：O(n2)
其中n是字符串的长度。
三、总结
由于状态g[l[r]依赖于状态g[l+1][r-1]，因此遍历左端点l是从大到小，遍历右端点r是从小到大。
因此最终的遍历过程可以优化为：
- 右端点r一直往右移动
- 左端点l在r在左边开始，一直往左移动
