LeetCode 题解（11）：Triangle

本文主要是介绍LeetCode 题解（11）：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.

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.

题解：

动态规划。要求O(n)存储空间，n为层数而非元素个数。可由上至下查表，也可由下至上查表。由下至上查表的好处是最后可以直接在0位置读出最小值。此处提供有上至下查表的解法，20ms通过。查表时由后向前更改表值，可防止覆盖。

class Solution {
public:int minimumTotal(vector<vector<int> > &triangle) {assert(triangle.size() != 0);int* temp = new int[triangle.size()];temp[0] = triangle[0][0];for(int i = 1; i < triangle.size(); i++){for(int j = triangle[i].size() - 1; j >= 0; j--){if( j ==  0 )temp[j] = temp[j] + triangle[i][j];else if( j == triangle[i-1].size() )temp[j] = temp[j-1] + triangle[i][j];elsetemp[j] = findMin(temp[j]+triangle[i][j], temp[j-1]+triangle[i][j]);}}int min = 0x7FFFFFFF;for(size_t i = 0; i < triangle.size(); i++){min = temp[i] < min ? temp[i]:min; }return min;}static int findMin( int a, int b){if( a >= b )return b;elsereturn a;    }
};

这篇关于LeetCode 题解（11）：Triangle的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---