Description
Given a triangle array, return the minimum path sum from top to bottom.
For each step, you may move to an adjacent number of the row below. More formally, if you are on index i on the current row, you may move to either index i or index i + 1 on the next row.
Solution
This problem could be solved with dynamic programming and we could do it in place using the input triangle. For every layer of the triangle, we also maintain a minimum sum for that layer. After we are done with the last layer of the triangle, the minimum sum will be the answer.
Implementation
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
int minimumTotal(vector<vector<int>>& triangle) {
int minTotal = triangle[0][0];
for (size_t i = 1; i < triangle.size(); i++) {
minTotal = INT_MAX;
for (size_t j = 0; j < i+1; 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]);
}
minTotal = min(minTotal, triangle[i][j]);
}
}
return minTotal;
}
};