题目描述：
思路1：
利用动态规划。由于空间复杂度的限制，直接在triangle数组上进行修改，即把triangle数组当作dp数组。当j == 0时（即每一行的第一个元素），triangle[i][j] += triangle[i - 1][j]；当j == col - 1时（即每一行的最后一个元素），triangle[i][j] += triangle[i - 1][j - 1]；其余情况，triangle[i][j] += min(triangle[i - 1][j - 1], triangle[i - 1][j])。
class Solution { public: int minimumTotal(vector<vector<int>>& triangle) { int row = triangle.size(); if (row <= 0)//判空 return 0; for(int i=1;i<row;i++) for (int j = 0;j < triangle[i].size();j++) { if (j == 0) triangle[i][j] += triangle[i - 1][j]; else if (j == triangle[i].size() - 1) triangle[i][j] += triangle[i - 1][j - 1]; else triangle[i][j] += min(triangle[i - 1][j - 1], triangle[i - 1][j]); } int minSum = INT_MAX; for (int k = 0;k < triangle[row - 1].size();k++)//在最后一行中找出最小的那个就是最小的和路径 if (triangle[row - 1][k] < minSum) minSum = triangle[row - 1][k]; return minSum; } };
思路2：题目要求O（n）的空间复杂度，所以复制三角形的最后一行作为dp数组，从下往上更新dp数组。对于dp数组中的元素j，将dp[j]和dp[j+1]比较取出较小者和第i行的j元素相加，以此来更新dp[j]。相当于自底向上，一步步确定走到每一个点之后再向下走的最短路径。
class Solution { public: int minimumTotal(vector<vector<int>>& triangle) { int row = triangle.size(); if (row <= 0)//判空 return 0; vector<int> dp(triangle.back());//triangle.back()返回triangle向量的最后个元素（最后一行）的引用 for (int i = row - 2;i >= 0;i--) for (int j = 0;j <= i;j++) dp[j] = min(dp[j], dp[j + 1]) + triangle[i][j]; return dp[0]; } };