【题目描述】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 is11(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)
【解题思路】自底向上。动态规划。 求解从上到下最小路径和，那么由底部将每一层到达当前位置的最小路径计算出来，计算方法底层相邻元素取小的并和当前位置元素相加，层层计算，那么最顶层就是最小路径和。 minPath[i] = min(minPath[i]+minPath[i+1])+triangle[k][i]
【考查内容】动态规划
class Solution { public: int minimumTotal(vector<vector<int> > &triangle) { int res = 0; vector<int> minLen(triangle.back()); //行内最多元素为三角形最底层 for(int layer=triangle.size()-2; layer >= 0; layer--){ for(int i=0;i<triangle[layer].size();i++) minLen[i] = min(minLen[i],minLen[i+1])+triangle[layer][i]; } return minLen[0]; } };