[LeetCode] 120. Triangle

轉自LeetCode

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

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.

<Solution>

這題是要找出三角形結構下，和會是最小的路徑

首先，要注意一下何謂三角形結構

以題目的範例說明，看 row2 : [3, 4]，和 row3 : [6, 5, 7]

對於 3 來說，它能走的路徑只有到 6 或 5

對於 4 來說，它能走的路徑只有到 5 或 7

那因為數值有可能有負值，所以必須算出所有情況後來找出最小值

一開始直覺是使用 DFS 來解，但是會 TLE

這題必須使用 DP 的方式來解才可以

因為題目還有要求最多使用 O(n) 的額外空間

所以這邊使用 bottom-up 的方式來思考從最後一行開始往上找

每次更新找到和上一行和是最小的值，這樣到第一行，唯一的一個值就是所要的最小值

用題目的例子來舉例

code 如下 (參考資料)

	class Solution {
	public:
	int minimumTotal(vector<vector<int>>& triangle) {
	vector<int> ans(triangle.back());
	//> use dp algorithm
	//> start from the bottom row
	for(int i = triangle.size()-2; i > -1; i--) {
	for(int j = 0; j < triangle[i].size(); j++) {
	ans[j] = min(triangle[i][j] + ans[j], triangle[i][j] + ans[j+1]);
	}
	}
	return ans[0];
	}
	};

view raw minSumPathOfTriangle_1.cpp hosted with ❤ by GitHub