> For the complete documentation index, see [llms.txt](https://protegejj.gitbook.io/algorithm-practice/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://protegejj.gitbook.io/algorithm-practice/leetcode/dynamic-programming/interval-dp/132-palindrome-partitioning-ii.md).

# 132     Palindrome Partitioning II

## 132. [Palindrome Partitioning II](https://leetcode.com/problems/palindrome-partitioning-ii/description/)

## 1. Question

Given a strings, partitionssuch that every substring of the partition is a palindrome.

Return the minimum cuts needed for a palindrome partitioning ofs.

For example, givens=`"aab"`,\
Return`1`since the palindrome partitioning`["aa","b"]`could be produced using 1 cut.

## 2. Implementation

**(1) DP**

思路:

```java
class Solution {
    public int minCut(String s) {
        if (s == null || s.length() <= 1) {
            return 0;
        }

        int n = s.length();
        // isPalindrome[i][j]指的是s[i...j]是否是palindrome
        boolean[][] isPalindrome = new boolean[n][n];

        for (int i = 0; i < n; i++) {
            isPalindrome[i][i] = true;
        }

        // 区间DP模型:
        // Outer for loop 枚举区间长度
        // Inner for loop 枚举区间的起点
        for (int len = 2; len <= n; len++) {
            for (int start = 0; start < n - len + 1; start++) {
                int end = start + len - 1;

                if (len == 2) {
                    if (s.charAt(start) == s.charAt(end)) {
                        isPalindrome[start][end] = true;
                    }
                }
                else {
                    if (s.charAt(start) == s.charAt(end) && isPalindrome[start + 1][end - 1]) {
                        isPalindrome[start][end] = true;
                    }
                }
            }
        }

        // cuts[i] 表示在s[0...i]中分割palindromes所需要的最小cuts
        int[] cuts = new int[n];

        for (int i = 0; i < n; i++) {
            if (isPalindrome[0][i]) {
                cuts[i] = 0;
            }
            else {
                // s[0...i]最多可以有i个cuts将s分割成palindrome
                cuts[i] = i;
                for (int j = 0; j < i; j++) {
                    // 注意这里判断s[j + 1...i]是否是palindrome，如果是的话, 那么s[0...i]所需要的最小cut就是
                    // s[0...i] 与 s[0...j] + 1(因为s[j + 1... i]是palindrome, 要在s[j]后cut一次得到这个palindrome， 所以加1)之间的
                    // 较小值
                    if (isPalindrome[j + 1][i]) {
                        cuts[i] = Math.min(cuts[i], cuts[j] + 1);
                    }
                }
            }
        }
        return cuts[n - 1];
    }
}
```

## 3. Time & Space Complexity

**DP:** 时间复杂度O(n^2), 空间复杂度O(n^2)