Triangle

• Lintcode : 109 / Leetcode : 120
• Level : Medium

Problem

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

Example
Example 1:

Input the following triangle:
[
     [2],
    [3,4],
   [6,5,7],
  [4,1,8,3]
]
Output: 11
Explanation: The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11).
Example 2:

Input the following triangle:
[
     [2],
    [3,2],
   [6,5,7],
  [4,4,8,1]
]
Output: 12
Explanation: The minimum path sum from top to bottom is 12 (i.e., 2 + 2 + 7 + 1 = 12).
Notice
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.

Concept & Algorithm

筆記

Time Complexity & Space Complexity

time : O((1 + n) * n / 2) n:最底元素
space: O(n)

Answer

class Solution {
public:
    int minimumTotal(vector<vector<int>> &triangle) {
        int n = triangle.size();
        vector<int> dp(triangle[n - 1].size(), 0);
        dp[0] = triangle[0][0];
        for (int i = 1; i < n; i++) {
            for (int j = triangle[i].size() - 1; j >= 0; j--) {
                if (j == 0) dp[j] = dp[j] + triangle[i][j];
                else if (j == triangle[i].size() - 1) dp[j] = dp[j - 1] + triangle[i][j];
                else dp[j] = min(dp[j], dp[j - 1]) + triangle[i][j];
            }
        }
        int mini = INT_MAX;
        for (auto i : dp) {
            mini = min(i, mini);
        }
        return mini;
    }
};

tags: DP

​