6ms DP Solution with O(n) time & O(1) space!


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

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.