LeetCode 132: Palindrome Partitioning II

Given a string s, partition s such that every substring of the partition is a palindrome.
Return the minimum cuts needed for a palindrome partitioning of s.
For example, given s = "aab",
Return 1 since the palindrome partitioning ["aa","b"] could be produced using 1 cut.

public class Solution {
    public int minCut(String s) {
        // DP problem
        int n = s.length();
        
        // cut[i] represents minimum number of cuts for the first i characters
        int[] cut = new int[n+1];
        
        // Initialize 'cut' according to the worse case (cutted by each character).
        for (int i = 0; i <= n; i++)
            cut[i] = i-1;
            
        for (int i = 0; i < n; i++)
        {
            // Odd length palindrome
            // j represents the distance to i.
            for (int j = 0; i-j>=0 && i+j<n && s.charAt(i-j)==s.charAt(i+j); j++)
                // 1 of '1+cut[i-j]' means already verified palindrome
                // Note: cut[i+j+1] represents the 's' index range [0, i+j]
                cut[i+j+1] = Math.min(cut[i+j+1],1+cut[i-j]);

            // Even length palindrome
            for (int j = 1; i-j+1>=0 && i+j<n && s.charAt(i-j+1)==s.charAt(i+j); j++)
                cut[i+j+1] = Math.min(cut[i+j+1],1+cut[i-j+1]);
        }
        
        return cut[n];
    }
}