1
class Solution {
2
 public:
3
  int travel(vector<vector<int>> &tr, int lvl, int ind) {
4
    if (ind >= tr[lvl].size()) // To check if we are going out of bound
5
      return INT_MAX;
6

7
    if (lvl == tr.size() - 1) { // Return if we are on last line
8
      return tr[lvl][ind];
9
    }
10

11
    int s = travel(tr, lvl + 1, ind);      // Go South
12
    int se = travel(tr, lvl + 1, ind + 1); // Go South East
13

14
    // Return the minimum of south and south east + cost of the index we are
15
    // currently at.
16

17
    return min(s, se) + tr[lvl][ind];
18
  }
19

20
  int minimumTotal(vector<vector<int>> &triangle) {
21
    return travel(triangle, 0, 0);
22
  }
23
};