Here is a solution using dynamic programming. The naive solution would be a DFS, starting from the root at the top and navigating all subtrees below. Doing this, you end up computing certain values multiple times - as you may reach to them from multiple path upward.

The solution is to do it the other way around: bottom- up using dynamic programming:

- maintain the current known mins in a array, initialized with the last row

- for each new row, update the min based of previously computed values

public class Solution {

public int minimumTotal(List<List<Integer>> triangle) {

int min[] = new int[ triangle.size() ];

List<Integer> row = triangle.get( triangle.size() - 1);

for( int j = 0; j < row.size(); j++)

min[ j ] = row.get( j );

for( int i = triangle.size()-2; i >= 0; i--){

row = triangle.get( i );

for( int j =0 ; j < row.size(); j++){

int a = row.get( j );

a += min[j] > min[j+1] ? min[j+1] : min[j];

min[ j ] =a;

}

}

return min[0];

}

}