ArrayList
of ArrayList
s of integers, with each list representing a level of the triangle, find the minimum sum achieved by following a top-down path and adding the integer at each level along the path. Movement is restricted to adjacent numbers from the top to the bottom.Input Triangle:
[ [1],
[2, 3],
[4, 5, 6],
[7, 8, 9, 10],
]
Output : 14 (1->2->4->7)
Note: [..] denotes an ArrayList
int[] outBuffer
= new
int[input.get(height-1).size()];
. Fill this buffer array with the last row of the triangle. Now, move up the triangle, and at each level, iterate across the level and add to the base buffer the minimum sum of the element directly above - outBuffer[i]
= row.get(i)
+ Math.min(outBuffer[i],
outBuffer[i+1]);
. Finally, return the first element of the buffer - return outBuffer[0];
public static int minTriangleDepth(ArrayList<ArrayList<Integer>> input) { }
C
Java
Python