Simple top-down Java solution - O(n) space


  • 1
    L

    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.


  • 0
    R

    Same top-down idea with O(1) space. However, obviously bottom-up solution is much better for this case.

        public int minimumTotal(List<List<Integer>> triangle) {
        int n = triangle.size(), value1, value2;
        for(int i = 1; i < n; i++){
            for(int j = 0; j <= i; j++){
                if(j == 0){
                    value1 = triangle.get(i - 1).get(0);
                }else{
                    value1 = j == i ? triangle.get(i - 1).get(j - 1) : Math.min(triangle.get(i - 1).get(j - 1), triangle.get(i - 1).get(j));
                }
                value2 = triangle.get(i).get(j);
                triangle.get(i).set(j, value1 + value2);
            }
        }
        int min = Integer.MAX_VALUE;
        for(int k = 0; k < n; k++){
            min = Math.min(min, triangle.get(n - 1).get(k));
        }
        return min;
    }

  • 0
    F

    Sir, can I ask you one question? if the input is [[-1],[2,3],[1,-1,-3]], then what is expected output?? i thought is -2 where -1+2+-3 but the leetcode answer is -1. I don't get it. We should find the minimum number in each layer right? So for [2,3], the minimum should be 2 not 3. Then it cannot be -1+3+-3 = -1. Am i wrong???


  • 0
    R
    1. The expected output is -1, if you choose to take 2 in the second stage, you won't be able to take -3 in the third stage because they are not adjacent.
    2. You can choose the minimum number in each layer, what you are describing is a greedy solution. However this strategy does not guarantee an optimal solution.

Log in to reply
 

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