Minimize the sum after choosing elements from the given three arrays | Python3 implementation of the above approach ; Function to return the minimized sum ; If all the indices have been used ; If this value is pre - calculated then return its value from dp array instead of re - computing it ; If A [ i - 1 ] was chosen previously then only B [ i ] or C [ i ] can chosen now choose the one which leads to the minimum sum ; If B [ i - 1 ] was chosen previously then only A [ i ] or C [ i ] can chosen now choose the one which leads to the minimum sum ; If C [ i - 1 ] was chosen previously then only A [ i ] or B [ i ] can chosen now choose the one which leads to the minimum sum ; Driver code ; Initialize the dp [ ] [ ] array ; min ( start with A [ 0 ] , start with B [ 0 ] , start with C [ 0 ] )
import numpy as np NEW_LINE SIZE = 3 ; NEW_LINE N = 3 ; NEW_LINE def minSum ( A , B , C , i , n , curr , dp ) : NEW_LINE INDENT if ( n <= 0 ) : NEW_LINE INDENT return 0 ; NEW_LINE DEDENT if ( dp [ n ] [ curr ] != - 1 ) : NEW_LINE INDENT return dp [ n ] [ curr ] ; NEW_LINE DEDENT if ( curr == 0 ) : NEW_LINE INDENT dp [ n ] [ curr ] = min ( B [ i ] + minSum ( A , B , C , i + 1 , n - 1 , 1 , dp ) , C [ i ] + minSum ( A , B , C , i + 1 , n - 1 , 2 , dp ) ) ; NEW_LINE return dp [ n ] [ curr ] NEW_LINE DEDENT if ( curr == 1 ) : NEW_LINE INDENT dp [ n ] [ curr ] = min ( A [ i ] + minSum ( A , B , C , i + 1 , n - 1 , 0 , dp ) , C [ i ] + minSum ( A , B , C , i + 1 , n - 1 , 2 , dp ) ) ; NEW_LINE return dp [ n ] [ curr ] NEW_LINE DEDENT dp [ n ] [ curr ] = min ( A [ i ] + minSum ( A , B , C , i + 1 , n - 1 , 0 , dp ) , B [ i ] + minSum ( A , B , C , i + 1 , n - 1 , 1 , dp ) ) ; NEW_LINE return dp [ n ] [ curr ] NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT A = [ 1 , 50 , 1 ] ; NEW_LINE B = [ 50 , 50 , 50 ] ; NEW_LINE C = [ 50 , 50 , 50 ] ; NEW_LINE dp = np . zeros ( ( SIZE , N ) ) ; NEW_LINE for i in range ( SIZE ) : NEW_LINE INDENT for j in range ( N ) : NEW_LINE INDENT dp [ i ] [ j ] = - 1 ; NEW_LINE DEDENT DEDENT print ( min ( A [ 0 ] + minSum ( A , B , C , 1 , SIZE - 1 , 0 , dp ) , min ( B [ 0 ] + minSum ( A , B , C , 1 , SIZE - 1 , 1 , dp ) , C [ 0 ] + minSum ( A , B , C , 1 , SIZE - 1 , 2 , dp ) ) ) ) ; NEW_LINE DEDENT