Minimum length of the reduced Array formed using given operations | C # 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
using System ; class GFG { static int minimalLength ( int [ ] a , int n ) { int [ , ] dp = new int [ n + 1 , n + 1 ] ; int [ ] dp1 = new int [ n ] ; int i , j , k ; for ( i = 0 ; i < n + 1 ; i ++ ) { for ( j = 0 ; j < n + 1 ; j ++ ) { dp [ i , j ] = - 1 ; } } for ( int size = 1 ; size <= n ; size ++ ) { for ( i = 0 ; i < n - size + 1 ; i ++ ) { j = i + size - 1 ; if ( i == j ) dp [ i , j ] = a [ i ] ; else { for ( k = i ; k < j ; k ++ ) { if ( dp [ i , k ] != - 1 && dp [ i , k ] == dp [ k + 1 , j ] ) dp [ i , j ] = dp [ i , k ] + 1 ; } } } } for ( i = 0 ; i < n ; i ++ ) dp1 [ i ] = ( int ) 1e7 ; for ( i = 0 ; i < n ; i ++ ) { for ( j = 0 ; j <= i ; j ++ ) { if ( dp [ j , i ] != - 1 ) { if ( j == 0 ) dp1 [ i ] = 1 ; else dp1 [ i ] = Math . Min ( dp1 [ i ] , dp1 [ j - 1 ] + 1 ) ; } } } return dp1 [ n - 1 ] ; } public static void Main ( string [ ] args ) { int n = 7 ; int [ ] a = { 3 , 3 , 4 , 4 , 4 , 3 , 3 } ; Console . Write ( minimalLength ( a , n ) ) ; } }