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
< ? php function minSumPath ( & $ A ) { $ memo = array ( ) ; for ( $ i = 0 ; $ i < count ( $ A ) ; $ i ++ ) $ memo [ $ i ] = 0 ; $ n = count ( $ A ) - 1 ; for ( $ i = 0 ; $ i < count ( $ A [ $ n ] ) ; $ i ++ ) $ memo [ $ i ] = $ A [ $ n ] [ $ i ] ; for ( $ i = count ( $ A ) - 2 ; $ i >= 0 ; $ i -- ) for ( $ j = 0 ; $ j < count ( $ A [ $ i + 1 ] ) - 1 ; $ j ++ ) $ memo [ $ j ] = $ A [ $ i ] [ $ j ] + min ( $ memo [ $ j ] , $ memo [ $ j + 1 ] ) ; return $ memo [ 0 ] ; } $ A = array ( array ( 2 ) , array ( 3 , 9 ) , array ( 1 , 6 , 7 ) ) ; echo ( minSumPath ( $ A ) ) ; ? >