C++ accepted solution


  • 0
    G

    Recursive solution with carrying reused computations in a hash table.

    class Solution {
    public:
        int minimumTotal(vector<vector<int>>& triangle) {
            return findMinimum(triangle, 0, 0);
        }
        
        int findMinimum(vector<vector<int>>& triangle, int level, int index)
        {
            if (level >= triangle.size())
                return 0;
            int key = level*(level+1)/2 + index;
            auto it = sums.find(key);
            if (it != sums.end())
                return it->second;
            int sum = triangle[level][index] + min(findMinimum(triangle, level+1, index), findMinimum(triangle, level+1, index+1));
            if (index > 0 && index < level)
                sums.insert(make_pair(key, sum));
            return sum;
        }
    private:
        unordered_map<int, int> sums;
    };
    

    Bottom-up solution, has only O(n) complexity.

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

Log in to reply
 

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