Palindrome Partitioning II

Given a string A, partition A such that every substring of the partition is a palindrome.

Return the minimum cuts needed for a palindrome partitioning of A.

The first and the only argument contains the string A.

Return an integer, representing the answer as described in the problem statement.

1 <= length(A) <= 501

Input 1:
    A = "aba"

Output 1:
    0

Explanation 1:
    "aba" is already a palindrome, so no cuts are needed.

Input 2:
    A = "aab"
    
Output 2:
    1

Explanation 2:
    Return 1 since the palindrome partitioning ["aa","b"] could be produced using 1 cut.

Solution:

Time: O(n^3)
Space: O(n^2)

public class Solution {
    public int minCut(String A) {
        // dp[i][j] = min cut requried for ith to jth
        // dp[i][j] = min(dp[i][k] + dp[k][j] + 1)
        // dp[i][i] = 0
        // dp[1][n]
        int n = A.length();
        int[][] dp = new int[n + 1][n + 1];
        for (int len = 0; len < n; len ++) {
            for (int i = 1; i <= n; i ++) {
                int j = i + len;
                if (i == j) {
                    dp[i][j] = 0;
                } else if (j <= n) {
                    dp[i][j] = len;
                    if (isP(A.substring(i - 1, j))) {
                        dp[i][j] = 0;
                    } else {
                        for (int k = i; k < j; k ++) {
                            dp[i][j] = Math.min(dp[i][j], dp[i][k] + dp[k + 1][j] + 1);
                        }
                    }
                }
            }
        }
        // for (int[] a : dp) {
        //     System.out.println(Arrays.toString(a));
        // }
        return dp[1][n];
    }
    
    private boolean isP(String A) {
        int left = 0;
        int right = A.length() - 1;
        while (left < right) {
            if (A.charAt(left) != A.charAt(right)) {
                return false;
            }
            left ++;
            right --;
        }
        return true;
    }
}