Sharing my intuitive algorithm (top down)


  • 0
    P

    I have commented out the section i think i have used differently. The overall algorithm is still the same, except for going from right to left while updating the resulting array and using j==i to check the right side border condition.

    I have intentionally kept the formatting the way it is for better readability.

    class Solution {
    public:
        int minimumTotal(vector<vector<int>>& triangle) {
            
            if(triangle.size()==0)
            {
                return 0;
            }
            
            int row= triangle.size();
            int col = triangle[row-1].size();
            int minima = INT_MAX;
            
            vector<int> final(col, INT_MAX);
            final[0]= triangle[0][0];
            
            for(int i = 1; i < row; i++)
            {
                for(int j = i; j >= 0; j-- ) //going from back to front is a lot easier 
                //as it doesn't mess up with the values we need for calculation
                {
                    if (j==0)
                    {
                        final[j] = triangle[i][j] + final[j];
                    }
                    else if (j==i) //right border check
                    {
                        final[j] = triangle[i][j] + final[j-1];
                    }
                    else
                    {
                        final[j] = triangle[i][j] + min(final[j], final[j-1] );
                    }
                }
            }
            
            for(int i = 0; i < col; i++)
            {
                 minima = min(minima, final[i]);
            }
            return minima;
        }
    };
    

Log in to reply
 

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