# DP Python Solution

• ``````class Solution:
# @param triangle, a list of lists of integers
# @return an integer

def minimumTotal(self, triangle):
R = len(triangle)
for i in range(R)[::-1]:
if i == R-1:
m = triangle[R-1]
else:
for j in range(i+1):
m[j] = triangle[i][j] + min(m[j], m[j+1])

return m[0]``````

• c++ DP solution (12ms)

``````int minimumTotal(vector<vector<int> > &triangle) {
int n = triangle.size();
if(n == 0)
return 0;
int sum=triangle[0][0], id=0, left, right;
vector<int> store; //array to store min values (bottom up manner)
//store the leaves in the array
for(int i=0; i<n; i++) {
store.push_back(triangle[n-1][i]);
}
for(int i=n-2; i>=0; i--) {
for(id=0; id<=i; id++) {
left = triangle[i][id] + store[id];
right = triangle[i][id] + store[id+1];
// update store array (ignore end values)
if(left<right)
store[id] = left;
else
store[id] = right;
}
}
return store[0]; //result will be first element

}``````

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