Minimum Sum Path in a Triangle | Util function to find minimum sum for a path ; For storing the result in a 1 - D array , and simultaneously updating the result . ; For the bottom row ; Calculation of the remaining rows , in bottom up manner . ; return the top element ; Driver Code
def minSumPath ( A ) : NEW_LINE INDENT memo = [ None ] * len ( A ) NEW_LINE n = len ( A ) - 1 NEW_LINE for i in range ( len ( A [ n ] ) ) : NEW_LINE INDENT memo [ i ] = A [ n ] [ i ] NEW_LINE DEDENT for i in range ( len ( A ) - 2 , - 1 , - 1 ) : NEW_LINE INDENT for j in range ( len ( A [ i ] ) ) : NEW_LINE INDENT memo [ j ] = A [ i ] [ j ] + min ( memo [ j ] , memo [ j + 1 ] ) ; NEW_LINE DEDENT DEDENT return memo [ 0 ] NEW_LINE DEDENT A = [ [ 2 ] , [ 3 , 9 ] , [ 1 , 6 , 7 ] ] NEW_LINE print ( minSumPath ( A ) ) NEW_LINE