8ms C++ code O(n^2) in time O(n) in space DP


  • 0
    J
    int minimumTotal(vector<vector<int>>& triangle) {
        if(triangle.size()==0) return 0;
        vector<int> m = triangle.back();
        int i = (int)triangle.size()-1;
        while (--i>=0)
            for (int j=0; j<=i; j++)
                m[j] = triangle[i][j] + min(m[j],m[j+1]);
        return m[0];
    }

Log in to reply
 

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