原题传送门

1. 题目描述

2. Solution 1

1、思路分析
1> 状态定义: dp[i] 表示以s[0, i]的最少分割次数。
2> 边界: dp[i] = i。至少，单个字符就是回文的。
3> 状态转移方程:
遍历s，设工作变量为mid，表示回文的中心位置。
case 1: s长度是奇数，中心位置在mid下标处，延伸至两端。
case 2: s长度是偶数，中心位置在[mid-1, mid]之间的缝，延伸至两端。

2、代码实现

package Q0199.Q0132PalindromePartitioningII;import java.util.stream.IntStream;public class Solution {    public int minCut(String s) {        // corner case        if (s == null || s.length() <= 1) return 0;        // dp        int n = s.length();        int[] dp = IntStream.range(0, n).toArray(); // initial value: dp[i] = i        for (int mid = 1; mid < n; mid++) {     // iterate through all chars as mid point of palindrome            // CASE 1. odd len, center is at index mid, expand on both sides            for (int start = mid, end = mid; start >= 0 && end < n && s.charAt(start) == s.charAt(end);                 start--, end++) {                int newCutAtEnd = (start == 0) ? 0 : dp[start - 1] + 1;                dp[end] = Math.min(dp[end], newCutAtEnd);            }            // CASE 2: even len, center is between [mid-1, mid], expand on both sides            for (int start = mid - 1, end = mid; start >= 0 && end < n && s.charAt(start) == s.charAt(end);                 start--, end++) {                int newCutAtEnd = (start == 0) ? 0 : dp[start - 1] + 1;                dp[end] = Math.min(dp[end], newCutAtEnd);            }        }        return dp[n - 1];    }}

3、复杂度分析
时间复杂度: O(n^2)
空间复杂度: O(n)