Minimum length of the reduced Array formed using given operations | Python3 implementation to find the minimum length of the array ; Function to find the length of minimized array ; Creating the required dp tables Initialising the dp table by - 1 ; base case ; Check if the two subarray can be combined ; Initialising dp1 table with max value ; Check if the subarray can be reduced to a single element ; Minimal partition of [ 1 : j - 1 ] + 1 ; Driver code
import numpy as np NEW_LINE def minimalLength ( a , n ) : NEW_LINE INDENT dp = np . ones ( ( n + 1 , n + 1 ) ) * - 1 ; NEW_LINE dp1 = [ 0 ] * n ; NEW_LINE for size in range ( 1 , n + 1 ) : NEW_LINE INDENT for i in range ( n - size + 1 ) : NEW_LINE INDENT j = i + size - 1 ; NEW_LINE if ( i == j ) : NEW_LINE INDENT dp [ i ] [ j ] = a [ i ] ; NEW_LINE DEDENT else : NEW_LINE INDENT for k in range ( i , j ) : NEW_LINE INDENT if ( dp [ i ] [ k ] != - 1 and dp [ i ] [ k ] == dp [ k + 1 ] [ j ] ) : NEW_LINE INDENT dp [ i ] [ j ] = dp [ i ] [ k ] + 1 ; NEW_LINE DEDENT DEDENT DEDENT DEDENT DEDENT for i in range ( n ) : NEW_LINE INDENT dp1 [ i ] = int ( 1e7 ) ; NEW_LINE DEDENT for i in range ( n ) : NEW_LINE INDENT for j in range ( i + 1 ) : NEW_LINE INDENT if ( dp [ j ] [ i ] != - 1 ) : NEW_LINE INDENT if ( j == 0 ) : NEW_LINE INDENT dp1 [ i ] = 1 ; NEW_LINE DEDENT else : NEW_LINE INDENT dp1 [ i ] = min ( dp1 [ i ] , dp1 [ j - 1 ] + 1 ) ; NEW_LINE DEDENT DEDENT DEDENT DEDENT return dp1 [ n - 1 ] ; NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT n = 7 ; NEW_LINE a = [ 3 , 3 , 4 , 4 , 4 , 3 , 3 ] ; NEW_LINE print ( minimalLength ( a , n ) ) ; NEW_LINE DEDENT