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.
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: DP
Time complexity: O(n^2)
Space complexity: O(1)
C++
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 |
// Author: Huahua // Running time: 4 ms class Solution { public: // [[2] [[2] // [3, 4]] [5, 6] // [6, 5, 7]] [11, 10, 11] // [4, 1, 8, 3]] [15, 11, 18, 14]] int minimumTotal(vector<vector<int>>& t) { int n = t.size(); // t[i][j] := minTotalOf(i,j) // t[i][j] += min(t[i - 1][j], t[i - 1][j - 1]) for (int i = 0; i < n; ++i) for (int j = 0; j <= i; ++j) { if (i == 0 && j == 0) continue; if (j == 0) t[i][j] += t[i - 1][j]; else if (j == i) t[i][j] += t[i - 1][j - 1]; else t[i][j] += min(t[i - 1][j], t[i - 1][j - 1]); } return *std::min_element(begin(t.back()), end(t.back())); } }; |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment