Accept Solution O(n^2)


  • 0
    L

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

Log in to reply
 

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