-
Notifications
You must be signed in to change notification settings - Fork 1
Expand file tree
/
Copy path120.cpp
More file actions
30 lines (27 loc) · 838 Bytes
/
120.cpp
File metadata and controls
30 lines (27 loc) · 838 Bytes
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
// Author: btjanaka (Bryon Tjanaka)
// Problem: (LeetCode) 120
// Title: Triangle
// Link: https://leetcode.com/problems/triangle/description/
// Idea: Dynamic programming -- at each index, you check the minimum path from
// the two cells on the previous row that could have led to it.
// Difficulty: Medium
// Tags:
class Solution {
public:
int minimumTotal(vector<vector<int>>& triangle) {
vector<int> row;
row.push_back(triangle[0][0]);
for (int i = 1; i < triangle.size(); ++i) {
vector<int> row2;
for (int j = 0; j < i + 1; ++j) {
row2.push_back(
min((j == 0) ? INT_MAX : row[j - 1], (j >= i) ? INT_MAX : row[j]) +
triangle[i][j]);
}
row = row2;
}
int min_path = INT_MAX;
for (int x : row) min_path = min(x, min_path);
return min_path;
}
};