Q23 Palindrome Partitioning II - LeetCode - 132 ( n^3 approach)

class Solution {
    public int minCut(String s) {
        /* dp playlist video 28 , first approach O(n^3)
        */

        //make boolean 2d array
        int n = s.length();
        boolean[][] arr = new boolean[n][n];

        
        //traversing diagonally up
        for(int gap = 0 ; gap < n ; gap++){

            for(int i = 0 , j = gap ; j < n ; i++ , j++){

                if(gap == 0)
                arr[i][j] = true;

                else if(gap == 1){
                    if(s.charAt(i) == s.charAt(j)) 
                    arr[i][j] = true;
                }
                

                else{
                    if(s.charAt(i) == s.charAt(j) && arr[i+1][j-1]==true)
                    arr[i][j] = true;
                }
                
            }
        }

        //now making int 2d array to store minimum cuts on every cell
        int [][] dp = new int[n][n];

        for(int gap = 0 ; gap < n ; gap++){

            for(int i = 0 , j = gap ; j < n ; i++ , j++){
                //handling trivial cases
                if(gap == 0)
                dp[i][j] = 0;

                else if(gap == 1){
                    if(s.charAt(i) != s.charAt(j))
                    dp[i][j] = 1;
                }
                    
                
                

                else{
                    //if word is already a pallindrome
                    if(arr[i][j] == true)
                    dp[i][j] = 0;
                    
                    else{
                        /* now checking every partion call for minimum
                        cuts(faith) left string will be [i , k]  
                        right will be [k+1 , j] find minimum cut faith call
                        */
                        int min = Integer.MAX_VALUE;
                        //k starts from i and ends on j
                        for(int k = i ; k < j ;k++){
                            int left = dp[i][k];
                            int right = dp[k+1][j];

                            min = Math.min(min,left + right);
                        }

                        dp[i][j] = min +1;  //add 1 for faith call

                        }
                }
            }
        }
        return dp[0][n-1];  //last coloumn of first row will have answer
    }
}