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
#include <bits/stdc++.h> NEW_LINE using namespace std ; int minimalLength ( int a [ ] , int n ) { int dp [ n + 1 ] [ n + 1 ] , dp1 [ n ] ; int i , j , k ; memset ( dp , -1 , sizeof ( dp ) ) ; 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 ] = 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 ] = min ( dp1 [ i ] , dp1 [ j - 1 ] + 1 ) ; } } } return dp1 [ n - 1 ] ; } int main ( ) { int n = 7 ; int a [ n ] = { 3 , 3 , 4 , 4 , 4 , 3 , 3 } ; cout << minimalLength ( a , n ) ; return 0 ; }