上文中我们寻找了分割回文串的所有方案。但是如果我们只需要知道最小分割次数，而不需要知道所有具体方案，我们可以使用动态规划来更高效地解决这个问题。
首先，我们定义动态规划的状态：
设 $dp[i]$ 表示将字符串 $s$ 从索引 $0$ 到索引 $i$ 的前缀子串 $s[0..i]$ 分割成若干个回文子串所需的最小切割次数。我们这里的索引 $i$ 的范围是从 $0$ 到 $n-1$，其中 $n$ 是字符串 $s$ 的长度。
我们的目标是计算 $dp[n-1]$。
接下来，考虑如何从已知状态计算 $dp[i]$。要计算 $s[0..i]$ 的最小切割次数，我们可以考虑最后一次切割（或不切割）。这意味着最后一块回文子串是 $s[j..i]$，其中 $j$ 是这个回文子串的起始索引，$0 \le j \le i$。
如果 $s[j..i]$ 是一个回文子串，那么将 $s[0..i]$ 分割成回文串的一种方案可以是：先将前面的子串 $s[0..j-1]$ 分割好（最优方案需要 $dp[j-1]$ 次切割），然后在索引 $j-1$ 和 $j$ 之间进行一次切割，将 $s[j..i]$ 作为最后一块。
这里需要分情况考虑 $j$ 的值：
- 如果 $j = 0$：这意味着最后一块回文子串是整个前缀 $s[0..i]$。如果 $s[0..i]$ 本身就是回文串，那么就不需要任何切割，此时的切割次数是 $0$。
- 如果 $j > 0$：这意味着最后一块回文子串是 $s[j..i]$。前面的子串是 $s[0..j-1]$。将 $s[0..i]$ 分割的次数就是将 $s[0..j-1]$ 分割的最小次数 $dp[j-1]$，再加上索引 $j-1$ 后面这一刀，所以是 $dp[j-1] + 1$ 次切割。
我们要求的是最小切割次数 $dp[i]$，所以需要考虑所有可能的起始索引 $j$ ($0 \le j \le i$)，只要 $s[j..i]$ 是回文串，它就提供了一种可能的分割方案。$dp[i]$ 就是所有这些有效方案中切割次数的最小值。
因此，状态转移方程可以写为：
$$dp[i] = \min_{0 \le j \le i \atop s[j..i] \text{ 是回文串}} { \text{cost}(j, i) }$$
其中，$\text{cost}(j, i)$ 是以 $s[j..i]$ 作为最后一块回文子串时的总切割次数，它是一个分段函数：
$$ \begin{cases} 0 & \text{if } j = 0, \ dp[j-1] + 1 & \text{if } j > 0 \end{cases} $$
将 $\text{cost}(j, i)$ 代入方程：
$$dp[i] = \min \left( \begin{cases} 0 & \text{if } 0 \le j \le i \text{ and } s[j..i] \text{ is palindrome and } j = 0, \ dp[j-1] + 1 & \text{if } 0 \le j \le i \text{ and } s[j..i] \text{ is palindrome and } j > 0 \end{cases} \right)$$
这个分段 min 函数可以简化表达。我们是在所有满足 $s[j..i]$ 是回文串的 $j$ 值中取最小值。如果 $j=0$ 且 $s[0..i]$ 是回文，最小就是 0。否则，如果存在其他 $j>0$ 使得 $s[j..i]$ 是回文，我们就取所有 $dp[j-1]+1$ 中的最小值，然后和可能存在的 0 比较。
更简洁的表达方式是：
对于 $i = 0, 1, \ldots, n-1$: $$dp[i] = \min_{0 \le j \le i \atop s[j..i] \text{ 是回文串}} \begin{cases} 0 & \text{if } j = 0, \ dp[j-1] + 1 & \text{if } j > 0 \end{cases}$$
基本情况：
$dp[0]$ 的计算：$i=0$。可能的 $j$ 只有 $0$。$s[0..0]$ 是回文串。$j=0$，cost 是 $0$。 $dp[0] = \min({0 \mid j=0, s[0..0] \text{ 是回文} }) = 0$。
在代码中，dp[i] = i 的初始化给 dp[i] 提供了一个初始上界（最坏情况下，$s[0..i]$ 需要 $i$ 次切割，即每次切割一个字符），然后通过内层循环不断用 dp[j-1] + 1 或 0 来尝试更新 dp[i] 取到更小值。
需要注意：
- 为了使这个 DP 高效，判断 “s[j..i] 是回文串” 需要是 O(1) 操作，这依赖于我们提前进行的 O(n^2) 预处理。
- DP 计算的顺序是 $i$ 从 $0$ 到 $n-1$，确保在计算 $dp[i]$ 时，$dp[j-1]$ (其中 $j-1 < i$) 的值已经被计算出来。
因此我们不能使用上文中的回文串判断方法，而是需要使用动态规划预处理出所有子串是否是回文串。我们建一个二维数组 isPalindrome，isPalindrome[i][j] 表示 $s[i..j]$ 是否是回文串。根据回文串的性质：
一个字符串是回文串，当且仅当它的首尾字符相同，并且去掉首尾，中间的子串也是回文串。
因此我们很自然地分3种情况：
- 单个字符，显然是回文串。
- 两个字符，如果相同，则是回文串。
- 多个字符，如果首尾字符相同，并且去掉首尾后中间的子串也是回文串，则它是回文串。
完整代码：
1public static int minCut(String s) {
2 int len = s.length();
3 // 首先构建回文子串表
4 boolean[][] isPalindrome = new boolean[len][len];
5 // 单个字符肯定是回文
6 for(int i=0;i<len;i++) {
7 isPalindrome[i][i] = true;
8 }
9 // 两个字符是回文，只需首尾相等
10 for(int i=0;i<len-1;i++) {
11 if(s.charAt(i)==s.charAt(i+1)) isPalindrome[i][i+1]=true;
12 }
13 // 处理3个及以上字符的子串
14 // 是回文，当且仅当首尾相等且去掉首尾仍然是回文
15 for(int curlen=3;curlen<=len;curlen++) {
16 for(int i=0;i<=len-curlen;i++) {
17 int right = i+curlen-1; // 计算右边界
18 isPalindrome[i][right] = (s.charAt(i) == s.charAt(right))
19 && isPalindrome[i+1][right-1];
20 }
21 }
22
23 // 然后，动态规划来求最小分割次数
24 int[] dp = new int[len];
25 // 初始化dp数组
26 // 如果是0，不需要分割（单个字符）。其他的取最坏情况，都要分割i次，即每个字符都要分割。
27 for(int i=0;i<len;i++) {
28 dp[i] = i;
29 }
30 for(int i=0;i<len;i++) {
31 for(int j=0;j<=i;j++) {
32 // 注意这里是j<=i，因为单字符串也是回文串，需要正确考虑
33 if(isPalindrome[j][i]) {
34 if(j==0) dp[i]=0;
35 else dp[i]=Math.min(dp[i], dp[j-1]+1);
36 // dp[i] 的当前值：它可能是我们为 s[0...i] 设置的初始“最坏情况”值 (i)，或者是之前在内层循环中，因为某个更小的 j' 值 (j' < j) 找到了一个更好的分割方案后更新过的值。它代表了到目前为止，我们已知的将 s[0...i] 分割成回文串的最小切割次数。
37 }
38 }
39 }
40
41 return dp[len-1];
42}
这样优化后的时间复杂度是 $O(n^2)$，空间复杂度也是 $O(n^2)$，比上文中的 $O(2^n)$ 要高效得多。