My C++ code (Bottom up DP, 8ms)


  • 10
    D

    Just do bottom up DP, it is easier and cleaner than top-down DP.

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

    // another version, without modifying the input array

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

  • 0

    Thank you for your elegant code.


Log in to reply
 

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