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.

&nbsp;
Example 1:

Input: triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]
Output: 11
Explanation: The triangle looks like:
   2
  3 4
 6 5 7
4 1 8 3
The minimum path sum from top to bottom is 2 + 3 + 5 + 1 = 11 (underlined above).


Example 2:

Input: triangle = [[-10]]
Output: -10


&nbsp;
Constraints:


	1 &lt;= triangle.length &lt;= 200
	triangle[0].length == 1
	triangle[i].length == triangle[i - 1].length + 1
	-104 &lt;= triangle[i][j] &lt;= 104


&nbsp;
Follow up: Could you&nbsp;do this using only O(n) extra space, where n is the total number of rows in the triangle?
class Solution:
    def minimumTotal(self, t: List[List[int]]) -> int:
        dp = []
        dp.append(t[0])
        
        r = len(t)
        answer = float('inf')
        for i in range(1, r):
            c = len(t[i])
            dp.append([])
            for j in range(0, c):
                if j == 0:
                    val = dp[i - 1][j] + t[i][j]
                elif j == c - 1:
                    val = dp[i - 1][j - 1] + t[i][j]
                else:
                    val = min(dp[i - 1][j], dp[i - 1][j - 1]) + t[i][j]
                if i == r - 1:
                    answer = min(answer, val)
                dp[i].append(val)
        return answer if r > 1 else t[0][0]
class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {

        int n = triangle.get( triangle.size() - 1).size();
        int dp[] = new int[n + 1];

        for(int i = triangle.size() - 1; i>=0; i--)
        {
            for(int j = 0; j<triangle.get(i).size(); j++)
                dp[j] = triangle.get(i).get(j) + Math.min(dp[j], dp[j+1]);
        }

        return dp[0];

    }
}
class Solution {
public:
    
    
    int travel(vector<vector<int>>& tr , int lvl , int ind) {
        
        if(ind >= tr[lvl].size()) // To check if we are going out of bound 
            return INT_MAX;
        
        if(lvl == tr.size() - 1) { // Return if we are on last line
            return tr[lvl][ind];
        }
        
        int s = travel(tr , lvl + 1, ind ); // Go South
        int se = travel(tr , lvl + 1 , ind + 1); // Go South East 
        
		// Return the minimum of south and south east + cost of the index we are currently at.
		
        return min(s , se) + tr[lvl][ind]; 
        
    }
    
    
    int minimumTotal(vector<vector<int>>& triangle) {
        return travel(triangle , 0 , 0);
    }
};
var minimumTotal = function(triangle) {
    const memo = {};
    
    function minPath(row, col) {
        let key = `${row}:${col}`;
        
        if (key in memo) {
            return memo[key];
        }
        
        let path = triangle[row][col];
        
        if (row < triangle.length - 1) {
            path += Math.min(minPath(row + 1, col), minPath(row + 1, col + 1));
        }
        
        memo[key] = path;
        
        return path;
    }
    
    return minPath(0, 0);
};
Triangle