Smallest subarray from a given Array with sum greater than or equal to K | Set 2 | C ++ program for the above approach ; Function to find the smallest subarray with sum greater than or equal target ; DP table to store the computed subproblems ; Initialize first column with 0 ; Initialize first row with 0 ; Check for invalid condition ; Fill up the dp table ; Print the minimum length ; Driver code
#include <bits/stdc++.h> NEW_LINE using namespace std ; int minlt ( vector < int > arr , int target , int n ) { vector < vector < int > > dp ( arr . size ( ) + 1 , vector < int > ( target + 1 , -1 ) ) ; for ( int i = 0 ; i < arr . size ( ) + 1 ; i ++ ) dp [ i ] [ 0 ] = 0 ; for ( int j = 0 ; j < target + 1 ; j ++ ) dp [ 0 ] [ j ] = INT_MAX ; for ( int i = 1 ; i <= arr . size ( ) ; i ++ ) { for ( int j = 1 ; j <= target ; j ++ ) { if ( arr [ i - 1 ] > j ) { dp [ i ] [ j ] = dp [ i - 1 ] [ j ] ; } else { dp [ i ] [ j ] = min ( dp [ i - 1 ] [ j ] , ( dp [ i ] [ j - arr [ i - 1 ] ] ) != INT_MAX ? ( dp [ i ] [ j - arr [ i - 1 ] ] + 1 ) : INT_MAX ) ; } } } if ( dp [ arr . size ( ) ] [ target ] == INT_MAX ) { return -1 ; } else { return dp [ arr . size ( ) ] [ target ] ; } } int main ( ) { vector < int > arr = { 2 , 3 , 5 , 4 , 1 } ; int target = 11 ; int n = arr . size ( ) ; cout << minlt ( arr , target , n ) ; }