leetcode 120. Triangle 红太狼 2022-08-21 02:20 126阅读 0赞 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. class Solution { public: int minimumTotal(vector<vector<int>>& triangle) { vector<vector<int>>uppersum(triangle.size()); uppersum[0].push_back(triangle[0][0]); for (int i = 1; i < triangle.size(); i++) { uppersum[i].resize(triangle[i].size()); uppersum[i][0] = uppersum[i - 1][0] + triangle[i][0]; uppersum[i].back() = uppersum[i - 1].back() + triangle[i].back(); for (int j = 1; j < triangle[i].size() - 1; j++) { uppersum[i][j] = triangle[i][j]; uppersum[i][j] += uppersum[i - 1][j - 1] < uppersum[i - 1][j] ? uppersum[i - 1][j - 1] : uppersum[i - 1][j]; } } int minsum = uppersum.back()[0]; for (int i = 1; i < triangle.back().size();i++) if (uppersum.back()[i] < minsum) minsum = uppersum.back()[i]; return minsum; } }; accepted
还没有评论,来说两句吧...