Minimum cost to select K strictly increasing elements | C ++ program for the above approach ; Function to calculate min cost to choose k increasing elements ; If k elements are counted return 0 ; If all elements of array has been traversed then return MAX_VALUE ; To check if this is already calculated ; When i 'th elements  is not considered ; When the ith element is greater than previous element check if adding its cost makes total cost minimum ; Driver code
#include <bits/stdc++.h> NEW_LINE using namespace std ; const int N = 1005 ; const int K = 20 ; int n , k ; int dp [ N + 1 ] [ N + 1 ] [ K + 1 ] ; int minCost ( int i , int prev , int cnt , int ele [ ] , int cost [ ] ) { if ( cnt == k + 1 ) { return 0 ; } if ( i == n + 1 ) { return 1e5 ; } int & ans = dp [ i ] [ prev ] [ cnt ] ; if ( ans != -1 ) { return ans ; } ans = minCost ( i + 1 , prev , cnt , ele , cost ) ; if ( ele [ i ] > ele [ prev ] ) { ans = min ( ans , cost [ i ] + minCost ( i + 1 , i , cnt + 1 , ele , cost ) ) ; } return ans ; } int main ( ) { memset ( dp , -1 , sizeof ( dp ) ) ; n = 4 ; k = 2 ; int ele [ n + 1 ] = { 0 , 2 , 6 , 4 , 8 } ; int cost [ n + 1 ] = { 0 , 40 , 20 , 30 , 10 } ; int ans = minCost ( 1 , 0 , 1 , ele , cost ) ; if ( ans == 1e5 ) { ans = -1 ; } cout << ans << endl ; return 0 ; }