三角形最小路径和

题解

首先分析题意： 自顶而下的找出最小路径和，且是下一层的相邻元素。

根据题意，可以使用一个大小为n的数组来存储每一层的累加和，即到每新的一层，计算当前点与上一层累加和中可以取最小值相加（因为是相邻结点，所以每个点可取的值最多就是俩个）

使用大小为n的数组来存储此值，从第一层往下依次计算，比如第二节点j， 使用arr存储每个累加和的话，arr[j] = min(arr[j], a[j + 1] ) + val[1][j], 但是由于arr[j- 1]刚结束，所以已经被覆盖为新的值，所以此时的结果是不对的。

• 此时就要使用一点技巧：

  从下面开始往上面进行每一层累加和，一方面可以避免覆盖至的问题，另一方面最后的arr[0]就是最后结果的最小值，而不用再去遍历arr，即 arr[j] = min(arr[j], arr[j+1]) + val[j]

  #include<iostream>
  #include<vector>
  using namespace std;
  // 三角形最小路径和
  // 要求空间复杂度是O（n）  n 为 三角形层数
    
  // 思路： 采用一个数组，存储已经计算好的和，到新的一层后，每个元素与其可以相加的已经计算好的元素的最小值相加 
  // 由于空间的限制，使用一个 n 大小的数组存储的时候，会使用被覆盖后的值，所以，从底层往上计算
    
  class Solution {
  public:
  	inline int min(int a, int b){
  		return a < b ? a : b;
  	}
  	int minimumTotal(vector<vector<int>>& triangle){
  		// 判断
  		if (triangle.size() == 0){
  			return 0;
  		}
  		// 初始化为最后一层
  		vector<int> arr = triangle[triangle.size() - 1];
  		for (int i = triangle.size() - 2; i >= 0; i--){
  			for (int j = 0; j < triangle[i].size(); j++){
  				arr[j] = triangle[i][j] + min(arr[j], arr[j + 1]);  // 刚好不会覆盖
  			}
  		}
  		return arr[0];
  	}
  };
    
    
  

---

• Previous
  LeetCode-5
• Next
  LeetCode-4