This is the solution I came up with. If n is the number of layers in the triangle, it requires O(n) storage and has running time is proportional to the number of elements in the triangle, so O(n^2).

The solution exploits the substructure that at each block in the triangle, the only way to get to that block is through either of its upstairs neighbors, and the minimum cost is the cheaper upstairs neighbor plus its own cost. Only the immediate upstairs costs are relevant.

```
public class Solution {
public int minimumTotal(List<List<Integer>> triangle) {
int[] upstairs = new int[triangle.size()];
int[] thisLevel = new int[triangle.size()];
upstairs[0] = triangle.get(0).get(0);
for (int i = 1; i < triangle.size(); i++){
List<Integer> ithRow = triangle.get(i);
for (int j = 0; j < i + 1; j++){
int jthcost = ithRow.get(j);
if (j == 0){ // beginning
thisLevel[j] = jthcost + upstairs[0];
} else if (j == i){ // end
thisLevel[j] = jthcost + upstairs[j - 1];
} else { // middle
thisLevel[j] = Math.min(upstairs[j - 1],upstairs[j]) + jthcost;
}
}
System.arraycopy(thisLevel, 0, upstairs, 0, i + 1);
}
return getMinimum(upstairs);
}
private int getMinimum(int[] array){
int min = Integer.MAX_VALUE;
for (int i = 0; i < array.length; i++){
if (array[i] < min) min = array[i];
}
return min;
}
}
```

[as is, the solution is wasteful in the constant copying from tempBest to currBest -- you could simply swap them every other row, but that would be a distraction.]

It seems to work. Thoughts?

end note -- This is also the solution that reeclapple supplies, except his uses Deques to their fullest instead of two arrays. For legibility, I think this solution deserves its own thread.