Lintcode: Triangle

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

Have you met this question in a real interview? 

Yes

Example

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

Note

Bonus point if you are able to do this using only O(n) extra space, where n is the total number of rows in the triangle.

Tags Expand 

Dynamic Programming

DP:
Naive way: use a two dimensional array, cal sum from top to bottom
Tip: how to creat a triangle array? use vector.resize()
s1: dp(i, j)  ---- min sum from start to (i,j)   -- i is row -- j is col
s2: if j == 0: dp(i, j) = dp( i - 1, j) + T(i, j)
      else if j == row.size() - 1: dp(i, j) = dp(i - 1, j - 1) + T(i, j)
      else dp(i, j) = min(dp(i - 1, j - 1), dp(i - 1, j)) + T(i, j)
s3: sort the last row of dp, choose the min one as result

Time has to be O(n!)
How to optimize space:
There are two situations:
when dp calculates from top to bottom(like the naive way):
        if we update dp value from left to right at each row, we will need at lease two n size vectors to store current dp row and previous dp row
        if we update dp value from right to left, we just need one n size vector and store current dp value to the same n size vector and will not affect next loop
when dp calculated from bottom to top:
        if we update dp value from left to right at each row, update  of dp value and store current result into the same dp vector directly will not affect the next loop
        if we update dp value from right to left at each row, we cannot store current result into the same dp vector which will affect next loop result.

From bottom to top with one vector
//reference: explanation has problem, see codes directly
http://www.cnblogs.com/TenosDoIt/p/3436532.html

Another trick way -----  used triangle array directly
http://yucoding.blogspot.com/2013/04/leetcode-question-112-triangle.html




Naive way:
Time: O(n!)
Space:O(n!)

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31

class Solution { public: /** * @param triangle: a list of lists of integers. * @return: An integer, minimum path sum. */ int minimumTotal(vector<vector<int> > &triangle) { // write your code here int rows = triangle.size(); if(rows == 0) return 0; //Define triangle array below or define [n*n] array directly //vector<vector<int> > dp(rows, vector<int>(rows)); vector<vector<int> > dp(rows); for(int i = 0; i < rows; i++){ dp[i].resize(i + 1); } dp[0][0] = triangle[0][0]; for(int i = 1; i < rows; i++){ for(int j = 0; j < triangle[i].size(); j++){ if( j == 0) dp[i][j] = dp[i - 1][j] + triangle[i][j]; else if(j == triangle[i].size() - 1) dp[i][j] = dp[i - 1][j - 1] + triangle[i][j]; else{ dp[i][j] = min(dp[i - 1][j - 1], dp[i - 1][j]) + triangle[i][j]; } } } sort(dp[rows - 1].begin(), dp[rows - 1].end()); return dp[rows - 1][0]; } };

Lintcode second:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27

class Solution { public: /** * @param triangle: a list of lists of integers. * @return: An integer, minimum path sum. */ int minimumTotal(vector<vector<int> > &triangle) { // write your code here if(triangle.size() == 0) return 0; int row = triangle.size(); int col = triangle[row - 1].size(); vector<vector<int> > dp(row, vector<int>(col, 0)); dp[0][0] = triangle[0][0]; for(int i = 1; i < row; i++){ for(int j = 0; j <= i; j++){ if(j == 0) dp[i][j] = dp[i - 1][j] + triangle[i][j]; else if(j == i) dp[i][j] = dp[i-1][j-1] + triangle[i][j]; else dp[i][j] = min(dp[i-1][j-1], dp[i-1][j]) + triangle[i][j]; } } int res=INT_MAX; for(int i = 0; i < col; i++){ res = min(res, dp[row - 1][i]); } return res; } };