132. Palindrome Partitioning II (區間型 + 一般 dp

T: O(n^2)

S: O(n^2)

```java
class Solution {
    public int minCut(String s) {
        int n = s.length();
        int[] dp = new int[n];
        Arrays.fill(dp, Integer.MAX_VALUE);

        // interval dp to memo is Palindrome for each [i][j]
        boolean[][] isPal = new boolean[n][n];
        for (int len = 1; len <= n; len++) {
            for (int i = 0; i <= n - len; i++) { // len 1, i = 0, j = 0 + 1-1 = 0,   i = n-1, j = n-1
                int j = i + len - 1;  // len: n, i = 0 , j = n-1
                if (s.charAt(i) == s.charAt(j)) {
                    if (j - i <= 2) { // dist only 2 or 1 or same, so it's Palindrome (ex: aba(len2) aa(len1), a(len0))
                        isPal[i][j] = true; // i == j, it means a Palindrome
                    } else {
                        //System.out.println("i:"+i + "j:"+ j +"len:"+ len);
                        isPal[i][j] = isPal[i+1][j-1]; // i+1, j-1 越界時代表很相近 (or use i+1 >= j-1, also means j - i <= 2)
                        // actually, 越界處理 i == j (j - i == 0) 這個狀況即可
                        // 但要正確答案, 要加上 j - i <= 2 也點是 true, 不然計算上是錯的
                        /**
                        像這個 下面兩個 應該也是 true
                        i:0j:0isPal:true
                        i:0j:1isPal:false
                        i:0j:2isPal:false
                         */
                    }
                }
            }
        }
        // for (int i = 0; i < n; i++) {
        //     for (int j = 0; j < n; j++) {
        //         System.out.println("i:"+i+"j:"+j + "isPal:"+ isPal[i][j]);
        //     }
        // }
        
        dp[0] = 1;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j <= i; j++) {
                if (isPal[j][i]) {
                    if (j == 0) {
                        dp[i] = 1; // is a isPalindrome , and j = 0, means j to i (start from 0 to i) is a isPalindrome, so only 1  Palindrome
                    } else {
                        dp[i] = Math.min(dp[i], dp[j-1]+1);
                    }
                }
            }
        }
        return dp[n-1]-1;
    }

    // private boolean isPalindrome(String s, int left, int right) {
    //     while (left < right) {
    //         if (s.charAt(left) != s.charAt(right)) {
    //             return false;
    //         } 
    //         left++;
    //         right--;
    //     }
    //     return true;
    // }
}

/**
        palindrome
xxxx [j.  i]
dp[i] = min(dp[i], dp[j-1]+1)

 dp[i]: how many palindrome in s[0:i]

 return dp[n-1]-1 (how many cuts for palindromes)

 */
```