# Accept Solution O(n^2)

• 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];
}

}
```

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.