7 lines neat Java Solution


  • 77
    Z
    public int minimumTotal(List<List<Integer>> triangle) {
        int[] A = new int[triangle.size()+1];
        for(int i=triangle.size()-1;i>=0;i--){
            for(int j=0;j<triangle.get(i).size();j++){
                A[j] = Math.min(A[j],A[j+1])+triangle.get(i).get(j);
            }
        }
        return A[0];
    }

  • 0
    R

    I don't understand, shouldn't the size of A be the length of base row of the triangle not the height of the triangle?


  • 2
    C

    I was confused too, here is why, level 1 have 1 node, level 2 have 2, nodes, and level n has n nodes. So triangle.size() = triangle.get(triangle.size()-1).size()


  • 0
    R

    Thanks, that makes sense


  • 0
    T

    Going backwards makes it much-much simpler!


  • 1
    K

    triangle is a list with multiple sublists and each sublist is a list of the nodes of one level, so triangle.size() is the number of sublists, the number of rows, the height of tree


  • 0

    Very smart! Still need quite some time to figure out how to come up this kinda nice solution. Thanks~


  • 2
    L

    Nice solution! The trick is to start from the last row, which really makes things much easier


  • 0
    R

    @robert8 from my understanding, he's using dp from bottom to top.


  • 1
    R

    Javascript version:

    var minimumTotal = function(triangle) {
        var A = new Array(triangle.length+1)
        A.fill(0)
        for(var i=triangle.length-1;i>=0;i--){
            for(var j=0;j<triangle[i].length;j++){
                A[j] = Math.min(A[j],A[j+1])+triangle[i][j];
            }
        }
        return A[0];        
    };
    

    Golang version:

    func minimumTotal(triangle [][]int) int {
        A:=make([]int, len(triangle) + 1)
        for k, _ :=range A {
            A[k] = 0
        }
        for i:=len(triangle)-1; i>=0; i-- {
            for j:=0; j < len(triangle[i]); j++ {
                A[j] = min(A[j], A[j+1]) + triangle[i][j] 
            }
        }
        return A[0]
    }
    
    func min(a int, b int) int {
        if a > b {
            return b
        } else {
            return a
        }
    }
    

  • 0
    Y
    This post is deleted!

  • 0
    E

    impressive!, it is hard to come up with something like this!


  • 0
    I

    DP from top to bottom:

    public int minimumTotal(List<List<Integer>> triangle) {
        int m = triangle.size();
        if (m == 0) return 0;
        int n = triangle.get(m - 1).size();
        if (n == 0) return 0;
        int[] dp = new int[m];
        dp[0] = triangle.get(0).get(0);
        for (int i = 1; i < m; i++) {
            int l = triangle.get(i).size();
            for (int k = l - 1; k >= 0; k--) {
                int curr = Math.min((k < l - 1 ? dp[k] : Integer.MAX_VALUE), 
                                    (k >= 1 ? dp[k - 1]: Integer.MAX_VALUE)) + triangle.get(i).get(k);
                dp[k] = curr;
            }
        }
        int min = Integer.MAX_VALUE;
        for (int k = 0; k < n; k++) {
            min = Math.min(min, dp[k]);
        }
        return min;
    }

  • 1
    B

    @ihaveayaya , for your top-to-bottom solution, it's better to make the inner for loop traverse from back to front, which will make it simpler.


  • 0
    I

    @binz Thanks for pointing out. I made a few changes to make the code a little bit simpler. If you think there is still room to optimize, please let me know.


Log in to reply
 

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