Minimize the sum of differences of consecutive elements after removing exactly K elements | Java implementation of the above approach . ; states of DP ; function to find minimum sum ; base - case ; if state is solved before , return ; marking the state as solved ; recurrence relation ; Driver function ; input values ; calling the required function ;
class GFG { final static int N = 100 ; final static int INF = 1000000 ; static int dp [ ] [ ] = new int [ N ] [ N ] ; static int vis [ ] [ ] = new int [ N ] [ N ] ; static int findSum ( int [ ] arr , int n , int k , int l , int r ) { if ( ( l ) + ( n - 1 - r ) == k ) return arr [ r ] - arr [ l ] ; if ( vis [ l ] [ r ] == 1 ) return dp [ l ] [ r ] ; vis [ l ] [ r ] = 1 ; dp [ l ] [ r ] = Math . min ( findSum ( arr , n , k , l , r - 1 ) , findSum ( arr , n , k , l + 1 , r ) ) ; return dp [ l ] [ r ] ; } public static void main ( String [ ] args ) { int arr [ ] = { 1 , 2 , 100 , 120 , 140 } ; int k = 2 ; int n = arr . length ; System . out . println ( findSum ( arr , n , k , 0 , n - 1 ) ) ; } }