Smallest subarray from a given Array with sum greater than or equal to K | Set 2 | Python3 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
import sys NEW_LINE def minlt ( arr , target , n ) : NEW_LINE INDENT dp = [ [ - 1 for _ in range ( target + 1 ) ] \ for _ in range ( len ( arr ) + 1 ) ] NEW_LINE for i in range ( len ( arr ) + 1 ) : NEW_LINE INDENT dp [ i ] [ 0 ] = 0 NEW_LINE DEDENT for j in range ( target + 1 ) : NEW_LINE INDENT dp [ 0 ] [ j ] = sys . maxsize NEW_LINE DEDENT for i in range ( 1 , len ( arr ) + 1 ) : NEW_LINE INDENT for j in range ( 1 , target + 1 ) : NEW_LINE INDENT if arr [ i - 1 ] > j : NEW_LINE INDENT dp [ i ] [ j ] = dp [ i - 1 ] [ j ] NEW_LINE DEDENT else : NEW_LINE INDENT dp [ i ] [ j ] = min ( dp [ i - 1 ] [ j ] ,   \ 1 + dp [ i ] [ j - arr [ i - 1 ] ] ) NEW_LINE DEDENT DEDENT DEDENT return dp [ - 1 ] [ - 1 ] NEW_LINE if dp [ - 1 ] [ - 1 ] == sys . maxsize : NEW_LINE INDENT return ( - 1 ) NEW_LINE DEDENT else : NEW_LINE INDENT return dp [ - 1 ] [ - 1 ] NEW_LINE DEDENT DEDENT arr = [ 2 , 3 , 5 , 4 , 1 ] NEW_LINE target = 11 NEW_LINE n = len ( arr ) NEW_LINE print ( minlt ( arr , target , n ) ) NEW_LINE