LeetCode - Triangle | Darren's Blog

Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below

For example, given the following triangle

[
     [2],
    [3,4],
   [6,5,7],
  [4,1,8,3]
]

The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11).

Bottom-Up: code from http://www.programcreek.com/2013/01/leetcode-triangle-java/

public int minimumTotal(ArrayList<ArrayList<Integer>> triangle) {
 int[] total = new int[triangle.size()];
 int l = triangle.size() - 1;
 
 for (int i = 0; i < triangle.get(l).size(); i++) {
  total[i] = triangle.get(l).get(i);
 }
 
 // iterate from last second row
 for (int i = triangle.size() - 2; i >= 0; i--) {
  for (int j = 0; j < triangle.get(i + 1).size() - 1; j++) {
   total[j] = triangle.get(i).get(j) + Math.min(total[j], total[j + 1]);
  }
 }
 
 return total[0];
}

Top-Down code from http://www.darrensunny.me/leetcode-triangle/
Let t and mps[i][j] denote the triangle and the minimum path sum from top to the j-th value in the i-th row, respectively. The following recursive equation can be observed:
t[i][j]=⎧⎩⎨mps[i−1][j]+t[i][j]mps[i−1][j−1]+t[i][j]min(t[i−1][j−1],t[i−1][j])+t[i][j]if j=0if j=iotherwise

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

        if (triangle == null || triangle.size() == 0)

            return 0;

 

        // mps: minimum path sums from top to row i

        int n = triangle.size();

        int[] mps = new int[n];

        mps[0] = triangle.get(0).get(0);

 

        // Work on each row one at a time

        for (int i = 1; i < n; i++) {

            ArrayList<Integer> currenRow = triangle.get(i);

            int temp1 = mps[0];     // Cache the value before it is overwritten

            mps[0] += currenRow.get(0);     // Only one path to the first value (all the way to the first)

            for (int j = 1; j < i; j++) {

                int temp2 = mps[j];     // Cache the value before it is overwritten

                mps[j] = Math.min(temp1, temp2) + currenRow.get(j); // Select the smaller from the two possible ways

                temp1 = temp2;

            }

            mps[i] = temp1 + currenRow.get(i);  // Only one path to the last value (all the way to the last)

        }

 

        // Find the minimum path sum from top to bottom

        int minimum = mps[0];

        for (int i = 1; i < n; i++) {

            minimum = Math.min(minimum, mps[i]);

        }

 

        return minimum;

    }

Top-Down: do it in place: code from http://yucoding.blogspot.com/2013/04/leetcode-question-112-triangle.html

int minimumTotal(vector<vector<int> > &triangle) {

        // Start typing your C/C++ solution below

        // DO NOT write int main() function

        int n = triangle.size();

        if (n==0){return 0;}

         

        for (int i=1;i<n;i++){

            for (int j=0;j<triangle[i].size();j++){

                if (j==0){triangle[i][j] += triangle[i-1][j];}

                if (j>0){

                    if (i>j){

                        triangle[i][j] += min(triangle[i-1][j-1],triangle[i-1][j]);

                    }else{

                        triangle[i][j] += triangle[i-1][j-1];

                    }

                     

                }

                 

            }

        }

        sort(triangle[n-1].begin(),triangle[n-1].end());

        return triangle[n-1][0];   

    }

Read full article from LeetCode - Triangle | Darren's Blog