Find minimum possible size of array with given rules for removing elements | Python3 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 program to test above function
MAX = 1000 NEW_LINE dp = [ [ - 1 for i in range ( MAX ) ] for i in range ( MAX ) ] NEW_LINE def minSizeRec ( arr , low , high , k ) : NEW_LINE INDENT if dp [ low ] [ high ] != - 1 : NEW_LINE INDENT return dp [ low ] [ high ] NEW_LINE DEDENT if ( high - low + 1 ) < 3 : NEW_LINE INDENT return ( high - low + 1 ) NEW_LINE DEDENT res = 1 + minSizeRec ( arr , low + 1 , high , k ) NEW_LINE for i in range ( low + 1 , high ) : NEW_LINE INDENT for j in range ( i + 1 , high + 1 ) : NEW_LINE INDENT if ( arr [ i ] == ( arr [ low ] + k ) and arr [ j ] == ( arr [ low ] + 2 * k ) and minSizeRec ( arr , low + 1 , i - 1 , k ) == 0 and minSizeRec ( arr , i + 1 , j - 1 , k ) == 0 ) : NEW_LINE INDENT res = min ( res , minSizeRec ( arr , j + 1 , high , k ) ) NEW_LINE DEDENT DEDENT DEDENT dp [ low ] [ high ] = res NEW_LINE return res NEW_LINE DEDENT def minSize ( arr , n , k ) : NEW_LINE INDENT dp = [ [ - 1 for i in range ( MAX ) ] for i in range ( MAX ) ] NEW_LINE return minSizeRec ( arr , 0 , n - 1 , k ) NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT arr = [ 2 , 3 , 4 , 5 , 6 , 4 ] NEW_LINE n = len ( arr ) NEW_LINE k = 1 NEW_LINE print ( minSize ( arr , n , k ) ) NEW_LINE DEDENT