Palindrom Partitioning

class Solution{
    static int palindromicPartition(String str)
    {
        // Minimum cuts to make all substring is palindrome
        int n = str.length();
        int[][] dp = new int[n][n];
        
        for (int gap=1; gap<n; gap++) {
            for (int row=0, col=gap; row<n-gap; row++, col++) {

                //  is palindrom hai to do nothing
                if (isPalindrome(str.substring(row, col+1))) {
                    dp[row][col] = 0;
                } else {
                    dp[row][col] = Integer.MAX_VALUE;
                    for (int k=row; k<col; k++) {
                        dp[row][col] = Math.min(dp[row][col], dp[row][k]+dp[k+1][col]+1);
                    }
                }
            }
        }
        
        return dp[0][n-1];  // Top-Right corner
    }
    
    private static boolean isPalindrome(String str) {
        int n = str.length();
        int left = 0;
        int right = n-1;
        
        while (left < right) {
            if (str.charAt(left) != str.charAt(right)) {
                return false;
            }
            left++;
            right--;
        }
        
        return true;
    }
}