Minimum sum subsequence such that at least one of every four consecutive elements is picked | Returns sum of minimum sum subsequence such that one of every four consecutive elements is picked from arr [ ] . ; dp [ i ] is going to store minimum sum subsequence of arr [ 0. . i ] such that arr [ i ] is part of the solution . Note that this may not be the best solution for subarray arr [ 0. . i ] ; If there is single value , we get the minimum sum equal to arr [ 0 ] ; If there are two values , we get the minimum sum equal to the minimum of two values ; If there are three values , return minimum of the three elements of array ; If there are four values , return minimum of the four elements of array ; Return the minimum of last 4 index ; Driver code
def minSum ( arr , n ) : NEW_LINE INDENT dp = [ 0 ] * n NEW_LINE if ( n == 1 ) : NEW_LINE INDENT return arr [ 0 ] NEW_LINE DEDENT if ( n == 2 ) : NEW_LINE INDENT return min ( arr [ 0 ] , arr [ 1 ] ) NEW_LINE DEDENT if ( n == 3 ) : NEW_LINE INDENT return min ( arr [ 0 ] , min ( arr [ 1 ] , arr [ 2 ] ) ) NEW_LINE DEDENT if ( n == 4 ) : NEW_LINE INDENT return min ( min ( arr [ 0 ] , arr [ 1 ] ) , min ( arr [ 2 ] , arr [ 3 ] ) ) NEW_LINE DEDENT dp [ 0 ] = arr [ 0 ] NEW_LINE dp [ 1 ] = arr [ 1 ] NEW_LINE dp [ 2 ] = arr [ 2 ] NEW_LINE dp [ 3 ] = arr [ 3 ] NEW_LINE for i in range ( 4 , n ) : NEW_LINE INDENT dp [ i ] = arr [ i ] + min ( min ( dp [ i - 1 ] , dp [ i - 2 ] ) , min ( dp [ i - 3 ] , dp [ i - 4 ] ) ) NEW_LINE DEDENT return min ( min ( dp [ n - 1 ] , dp [ n - 2 ] ) , min ( dp [ n - 4 ] , dp [ n - 3 ] ) ) NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT arr = [ 1 , 2 , 3 , 3 , 4 , 5 , 6 , 1 ] NEW_LINE n = len ( arr ) NEW_LINE print ( minSum ( arr , n ) ) NEW_LINE DEDENT