Minimum Sum Path in a Triangle | C # 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
using System ; using System . Collections . Generic ; using System . Linq ; class GFG { static int minSumPath ( ref List < List < int > > A ) { int [ ] memo = new int [ A . Count ] ; int n = A . Count - 1 ; for ( int i = 0 ; i < A [ n ] . Count ; i ++ ) memo [ i ] = A [ n ] [ i ] ; for ( int i = A . Count - 2 ; i >= 0 ; i -- ) for ( int j = 0 ; j < A [ i + 1 ] . Count - 1 ; j ++ ) memo [ j ] = A [ i ] [ j ] + ( int ) Math . Min ( memo [ j ] , memo [ j + 1 ] ) ; return memo [ 0 ] ; } public static void Main ( ) { List < List < int > > A = new List < List < int > > ( ) ; A . Add ( new List < int > { 2 } ) ; A . Add ( new List < int > { 3 , 9 } ) ; A . Add ( new List < int > { 1 , 6 , 7 } ) ; Console . WriteLine ( minSumPath ( ref A ) ) ; } }