Given a 'triangle' as an ArrayList of ArrayLists 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.
Note: - You can only traverse through adjacent nodes while moving up or down the triangle. - An adjacent node is defined as a node that is reached by moving down and left or down and right from a level. For eg, in the triangle shown below, if you are at the digit 3 in the second row, its adjacent nodes are 5 and 6
This problem can be made easier by carefully considering the shape of the data structure. A triangle is naturally the widest at its base, and becomes progressively narrower as you move up towards its top. This means that a bottom-up approach is the best way to go to solve this problem.
Use a buffer array that is the length of the base of the triangle - int outBuffer = newint[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;