Leetcode - Palindrome Partition 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.


Solution:
Using F_k denote the minimal partitioning of substring of s from char k to end of s
Then F_k = min_{k<=m < end} {if palindrome(k,m,s), F_{m+1} +1; else +\infty;}
where palindrome(k,m,s) = true if from char k to char m in string s is a sub palindrome.
calculate palindrome(k,m,s) can also be done in O(n^2), by dynamic programming.
The entire complexity is O(n^2)

public class Solution {  
    public int minCut(String s) {
        // Start typing your Java solution below
        // DO NOT write main() function
        int n = s.length();
        int[] d = new int[n + 1];
        d[n] = 0;
        d[n-1] = 1;
        boolean[][] map = new boolean[n][n];
        for(int i = 0; i < n; i++) {
            map[i][i] = true;
        }
        for(int l = 2; l <= n; l++){
            for(int j = 0; j + l -1 <= n-1; j++ ){
                if(j+1 <= j+l-2)
                    map[j][j+l-1] = s.charAt(j) == s.charAt(j+l-1) && map[j+1][j+l-2];
                else map[j][j+l-1] = s.charAt(j) == s.charAt(j+l-1);
            }
        }      
        for(int j = n-2; j >= 0; j--){
            int sum = n + 100;
            for(int m = n-1; m >= j; m--){
                if(map[j][m] ){
                    sum = Math.min(sum, 1 + d[m+1]);
                }
            }
            d[j] = sum;
        }
        return d[0]-1;
    }
}