# C++ accepted solution

• 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;
}
};
``````

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