Minimum sum subsequence such that at least one of every four consecutive elements is picked | function to calculate min sum using dp ; if elements are less than or equal to 4 ; save start four element as it is ; compute sum [ ] for all rest elements ; sum [ i ] = ar [ i ] + ( * min_element ( sum + i - 4 , sum + i ) ) ; ; Since one of the last 4 elements must be present ; Driver Code
def minSum ( ar , n ) : NEW_LINE INDENT if ( n <= 4 ) : NEW_LINE INDENT return min ( ar ) NEW_LINE DEDENT sum = [ 0 for i in range ( n ) ] NEW_LINE sum [ 0 ] = ar [ 0 ] NEW_LINE sum [ 1 ] = ar [ 1 ] NEW_LINE sum [ 2 ] = ar [ 2 ] NEW_LINE sum [ 3 ] = ar [ 3 ] NEW_LINE for i in range ( 4 , n ) : NEW_LINE INDENT sum [ i ] = ar [ i ] + min ( sum [ i - 4 : i ] ) NEW_LINE DEDENT return min ( sum [ n - 4 : n ] ) NEW_LINE DEDENT ar = [ 2 , 4 , 1 , 5 , 2 , 3 , 6 , 1 , 2 , 4 ] NEW_LINE n = len ( ar ) NEW_LINE print ( " Minimum ▁ sum ▁ = ▁ " , minSum ( ar , n ) ) NEW_LINE