Minimize the sum of differences of consecutive elements after removing exactly K elements | C ++ 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 ; callin the required function ;
#include <bits/stdc++.h> NEW_LINE using namespace std ; #define N  100 NEW_LINE #define INF  1000000 NEW_LINE int dp [ N ] [ N ] ; bool vis [ N ] [ N ] ; 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 ] ) return dp [ l ] [ r ] ; vis [ l ] [ r ] = 1 ; return dp [ l ] [ r ] = min ( findSum ( arr , n , k , l , r - 1 ) , findSum ( arr , n , k , l + 1 , r ) ) ; } int32_t main ( ) { int arr [ ] = { 1 , 2 , 100 , 120 , 140 } ; int k = 2 ; int n = sizeof ( arr ) / sizeof ( int ) ; cout << findSum ( arr , n , k , 0 , n - 1 ) ; }