Minimum possible sum of prices of a Triplet from the given Array | C ++ program to implement the above approach ; Function to minimize the sum of price by taking a triplet ; Initialize a dp [ ] array ; Stores the final result ; Iterate for all values till N ; Check if num [ j ] > num [ i ] ; Update dp [ j ] if it is greater than stored value ; Update the minimum sum as ans ; If there is no minimum sum exist then print - 1 else print the ans ; Driver Code
#include <iostream> NEW_LINE #include <bits/stdc++.h> NEW_LINE using namespace std ; long minSum ( int n , int num [ ] , int price [ ] ) { long dp [ n ] ; for ( int i = 0 ; i < n ; i ++ ) dp [ i ] = INT_MAX ; long ans = INT_MAX ; for ( int i = 0 ; i < n ; i ++ ) { for ( int j = i + 1 ; j < n ; j ++ ) { if ( num [ j ] > num [ i ] ) { dp [ j ] = ( long ) min ( ( long ) dp [ j ] , ( long ) price [ i ] + ( long ) price [ j ] ) ; ans = min ( ans , ( long ) dp [ i ] + ( long ) price [ j ] ) ; } } } return ans != INT_MAX ? ans : -1 ; } int main ( ) { int num [ ] = { 2 , 4 , 6 , 7 , 8 } ; int price [ ] = { 10 , 20 , 100 , 20 , 40 } ; int n = sizeof ( price ) / sizeof ( price [ 0 ] ) ; cout << ( minSum ( n , num , price ) ) ; }