Minimum Sum Path in a Triangle | Java program for Dynamic Programming implementation of Min 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
import java . io . * ; import java . util . * ; class GFG { static int A [ ] [ ] = { { 2 } , { 3 , 9 } , { 1 , 6 , 7 } } ; static int minSumPath ( ) { int [ ] memo = new int [ A . length ] ; int n = A . length - 1 ; for ( int i = 0 ; i < A [ n ] . length ; i ++ ) memo [ i ] = A [ n ] [ i ] ; for ( int i = A . length - 2 ; i >= 0 ; i -- ) for ( int j = 0 ; j < A [ i ] . length ; j ++ ) memo [ j ] = A [ i ] [ j ] + ( int ) Math . min ( memo [ j ] , memo [ j + 1 ] ) ; return memo [ 0 ] ; } public static void main ( String args [ ] ) { System . out . print ( minSumPath ( ) ) ; } }