Find minimum possible size of array with given rules for removing elements | Javascript program to find size of minimum possible array after removing elements according to given rules ; dp [ i ] [ j ] denotes the minimum number of elements left in the subarray arr [ i . . j ] . ; If already evaluated ; If size of array is less than 3 ; Initialize result as the case when first element is separated ( not removed using given rules ) ; Now consider all cases when first element forms a triplet and removed . Check for all possible triplets ( low , i , j ) ; Check if this triplet follows the given rules of removal . And elements between ' low ' and ' i ' , and between ' i ' and ' j ' can be recursively removed . ; Insert value in table and return result ; This function mainly initializes dp table and calls recursive function minSizeRec ; Driver code
let MAX = 1000 ; let dp = new Array ( MAX ) ; for ( let i = 0 ; i < MAX ; i ++ ) { dp [ i ] = new Array ( MAX ) ; for ( let j = 0 ; j < MAX ; j ++ ) { dp [ i ] [ j ] = 0 ; } } function minSizeRec ( arr , low , high , k ) { if ( dp [ low ] [ high ] != - 1 ) { return dp [ low ] [ high ] ; } if ( ( high - low + 1 ) < 3 ) { return high - low + 1 ; } let res = 1 + minSizeRec ( arr , low + 1 , high , k ) ; for ( let i = low + 1 ; i <= high - 1 ; i ++ ) { for ( let j = i + 1 ; j <= high ; j ++ ) { if ( arr [ i ] == ( arr [ low ] + k ) && arr [ j ] == ( arr [ low ] + 2 * k ) && minSizeRec ( arr , low + 1 , i - 1 , k ) == 0 && minSizeRec ( arr , i + 1 , j - 1 , k ) == 0 ) { res = Math . min ( res , minSizeRec ( arr , j + 1 , high , k ) ) ; } } } return ( dp [ low ] [ high ] = res ) ; } function minSize ( arr , n , k ) { for ( let i = 0 ; i < MAX ; i ++ ) { for ( let j = 0 ; j < MAX ; j ++ ) { dp [ i ] [ j ] = - 1 ; } } return minSizeRec ( arr , 0 , n - 1 , k ) ; } let arr = [ 2 , 3 , 4 , 5 , 6 , 4 ] ; let n = arr . length ; let k = 1 ; document . write ( minSize ( arr , n , k ) ) ;