Leetcode

Triangle

  • Time:O(n^2)
  • Space:O(1)

C++

class Solution {
 public:
  int minimumTotal(vector<vector<int>>& triangle) {
    for (int i = triangle.size() - 2; i >= 0; --i)
      for (int j = 0; j <= i; ++j)
        triangle[i][j] += min(triangle[i + 1][j], triangle[i + 1][j + 1]);
    return triangle[0][0];
  }
};

JAVA

class Solution {
  public int minimumTotal(List<List<Integer>> triangle) {
    for (int i = triangle.size() - 2; i >= 0; --i)
      for (int j = 0; j <= i; ++j)
        triangle.get(i).set(j, triangle.get(i).get(j) + Math.min(triangle.get(i + 1).get(j),
                                                                 triangle.get(i + 1).get(j + 1)));
    return triangle.get(0).get(0);
  }
}

Python

class Solution:
  def minimumTotal(self, triangle: List[List[int]]) -> int:
    for i in reversed(range(len(triangle) - 1)):
      for j in range(i + 1):
        triangle[i][j] += min(triangle[i + 1][j],
                              triangle[i + 1][j + 1])

    return triangle[0][0]