5 lines c++, short and sweet


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

  • 0

    Very smart solution, though the parameter triangle modified is a side effect. Anyway, quite smart one! Here is my direct solution using O(n) space.

    class Solution {
    public:
        int minimumTotal(vector<vector<int>>& triangle) 
        {
            int rowSize = triangle.size();
            if(!rowSize) return 0;
            int cur[rowSize]{0}, pre[rowSize]{0};
            pre[0] = triangle[0][0];
            for(int r = 1; r < rowSize; ++r)
            {
                for(int c = 0; c < triangle[r].size(); ++c)
                {
                    if(c == 0) cur[0] = pre[0]+triangle[r][0];
                    else if(c == triangle[r].size()-1) cur[c] = pre[c-1]+triangle[r][c];
                    else cur[c] = min(pre[c], pre[c-1])+triangle[r][c];
                }
                memcpy(pre, cur, sizeof(int)*rowSize);
            }
            int minSum = INT_MAX;
            for(int i = 0; i < rowSize; ++i) minSum = min(minSum, pre[i]);
            return minSum;
        }
    };

  • 0
    S

    @Yuanhui Why does this solution not work for top-bottom approach ?


  • 0
    Y

    @sujiths52 If you go from top to bottom, you have to check the minimum in the last row in the end. But I think it works.


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

Log in to reply
 

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