题解 | #三角形最小路径和#

dp动态规划

class Solution {
  public:
    int minTrace(vector<vector<int> >& triangle) {
      int size = triangle.size();
      // 从下往上递推会发生越界，维度加一
      std::vector<std::vector<int>> dp(size + 1, std::vector<int>(size + 1, 0));
      for (int i = size -1; i >= 0; i--) {
        for (int j = 0; j <= i; j++) {
          dp[i][j] = std::min(dp[i+1][j], dp[i+1][j+1]) + triangle[i][j];
          // 每一层都挑出最小的组成路径，直到最后唯一的出口
        }
      }
      return dp[0][0];
    }
};

优化

class Solution {
  public:
    int minTrace(vector<vector<int> >& triangle) {
      int size = triangle.size();
      std::vector<int> dp(size + 1, 0);
      for (int i = size - 1; i >= 0; i--) {
        for (int j = 0; j <= i; j++) {
          dp[j] = std::min(dp[j], dp[j+1]) + triangle[i][j];
          // 使用一维数组，每次覆盖刷新其值
        }
      }
      return dp[0];
    }
};