Accepted C++, 5 lines, DP, O(1) space

  • 0

    Bottum-up solution, reuse the existing vector to store the best path to that node from the bottom.

        int minimumTotal(vector<vector<int>>& t) {
            if (t.empty()) return 0;
            for(int i = t.size() - 2; i >= 0; i--)
                for(auto j=0; j<t[i].size(); j++)
                    t[i][j] = t[i][j] + min(t[i+1][j], t[i+1][j+1]);
            return t[0][0];

Log in to reply

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