Leetcode Triangle solution | easycpp

Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.

int minimumTotal(vector<vector<int> > &triangle) {

    int triangleSize = triangle.size();

    if(triangleSize == 0){

        return 0;

    }

    vector<int> saveMinDistance(triangle[triangleSize - 1].size() + 1, 0);

 

    int first,second,current;

    first = second = current = 0;

 

    for(int i = triangleSize - 1; i >=0; i--){

 

        for(int j = 0; j < i + 1; j++){

            current = triangle[i][j];

            first = current + saveMinDistance[j];

            second = current + saveMinDistance[j + 1];

 

            saveMinDistance[j] = first < second ? first : second;

        }

    }

    return saveMinDistance[0];

}

Read full article from Leetcode Triangle solution | easycpp