LeetCode - Triangle | Darren's Blog

Related: Leetcode 120 - Triangle
http://www.programcreek.com/2013/01/leetcode-triangle-java/
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/
http://www.cnblogs.com/Xylophone/p/3888822.html

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) {

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

    }

http://yuanbin.gitbooks.io/algorithm/content/dynamic_programming/triangle.html
Method 1 - Traverse without hashmap: 2^n
递归遍历，逐个累加所有自上而下的路径长度，最后返回这些不同的路径长度的最小值。由于每个点往下都有2条路径，使用此方法的时间复杂度约为 O(2^n)
​​ int minimumTotal(vector<vector<int> > &triangle) {

        if (triangle.empty()) {
            return -1;
        }
        int result = INT_MAX;
        dfs(0, 0, 0, triangle, result);
        return result;
    }
    void dfs(int x, int y, int sum, vector<vector<int> > &triangle, int &result) {
        const int n = triangle.size();
        if (x == n) {
            if (sum < result) {
                result = sum;
            }
            return;
        }
        dfs(x + 1, y, (sum + triangle[x][y]), triangle, result);
        dfs(x + 1, y + 1, (sum + triangle[x][y]), triangle, result);
    }

    int minimumTotal(vector<vector<int> > &triangle) {
        if (triangle.empty()) {
            return -1;
        }

        int result = INT_MAX;
        dfs(0, 0, 0, triangle, result);

        return result;
    }
    void dfs(int x, int y, int sum, vector<vector<int> > &triangle, int &result) {
        const int n = triangle.size();
        if (x == n) {
            if (sum < result) {
                result = sum;
            }
            return;
        }
        dfs(x + 1, y, (sum + triangle[x][y]), triangle, result);
        dfs(x + 1, y + 1, (sum + triangle[x][y]), triangle, result);
    }

Method 3 - Divide and Conquer with Cache

    int minimumTotal(vector<vector<int> > &triangle) {
        if (triangle.empty()) {
            return -1;
        }
        vector<vector<int> > hashmap(triangle);
        for (int i = 0; i != hashmap.size(); ++i) {
            for (int j = 0; j != hashmap[i].size(); ++j) {
                hashmap[i][j] = INT_MIN;
            }
        }
        int result = dfs(0, 0, triangle, hashmap);
        return result;
    }
    int dfs(int x, int y, vector<vector<int> > &triangle, vector<vector<int> > &hashmap) {
        const int n = triangle.size();
        if (x == n) {
            return 0;
        }
        // INT_MIN means no value yet
        if (hashmap[x][y] != INT_MIN) {
            return hashmap[x][y];
        }
        int x1y = dfs(x + 1, y, triangle, hashmap);
        int x1y1 = dfs(x + 1, y + 1, triangle, hashmap);
        hashmap[x][y] =  min(x1y, x1y1) + triangle[x][y];
        return hashmap[x][y];
    }

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