Share my O(n ^ 2) solution


  • 0
    O
    class Solution {
        public:
            int minimumTotal(vector<vector<int> > &triangle) {
                int n = (int)triangle.size();
                for(int i = n - 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];
            }
        };
    

    I go upwards. On each step I calculate minimum path sum from vertex to bottom. It's obvious that in triangle[0][0] we will have our answer.


Log in to reply
 

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