# Triangle – LeetCode Solution Java , Python 3, Python 2 , C , C++, Best and Optimal Solutions , All you need.

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.

**Example 1:**

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

**Example 2:**

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

**Constraints:**

`1 <= triangle.length <= 200`

`triangle[0].length == 1`

`triangle[i].length == triangle[i - 1].length + 1`

`-10`

^{4}<= triangle[i][j] <= 10^{4}

# C++ Triangle LeetCode Solution

class Solution {

public:

int dfs(int i, int j, int n, vector<vector<int>>& triangle) {

if (i == n) return 0;

int lower_left = triangle[i][j] + dfs(i + 1, j, n, triangle);

int lower_right = triangle[i][j] + dfs(i + 1, j + 1, n, triangle);

return min(lower_left, lower_right);

}

int minimumTotal(vector<vector<int>>& triangle) {

int n = triangle.size();

return dfs(0, 0, n, triangle);

}

};

# Java Triangle LeetCode Solution

```
``````
public int minimumTotal(List<List<Integer>> triangle) {
int[] A = new int[triangle.size()+1];
for(int i=triangle.size()-1;i>=0;i--){
for(int j=0;j<triangle.get(i).size();j++){
A[j] = Math.min(A[j],A[j+1])+triangle.get(i).get(j);
}
}
return A[0];
}
```

# Python 3 Triangle LeetCode Solution

class Solution:

def minimumTotal(self, triangle: List[List[int]]) -> int:

def dfs(i, j):

if i == len(triangle):

return 0lower_left = triangle[i][j] + dfs(i + 1, j)

lower_right = triangle[i][j] + dfs(i + 1, j + 1)return min(lower_left, lower_right)

return dfs(0, 0)

Array-1180

String-562

Hash Table-412

Dynamic Programming-390

Math-368

Sorting-264

Greedy-257

Depth-First Search-256

Database-215

Breadth-First Search-200

Tree-195

Binary Search-191

Matrix-176

Binary Tree-160

Two Pointers-151

Bit Manipulation-140

Stack-133

Heap (Priority Queue)-117

Design-116

Graph-108

Simulation-103

Prefix Sum-96

Backtracking-92

Counting-86

Sliding Window-73

Linked List-69

Union Find-66

Ordered Set-48

Monotonic Stack-47

Recursion-43

Trie-41

Binary Search Tree-40

Divide and Conquer-40

Enumeration-39

Bitmask-37

Queue-33

Memoization-32

Topological Sort-31

Geometry-30

Segment Tree-27

Game Theory-24

Hash Function-24

Binary Indexed Tree-21

Interactive-18

Data Stream-17

String Matching-17

Rolling Hash-17

Shortest Path-16

Number Theory-16

Combinatorics-15

Randomized-12

Monotonic Queue-9

Iterator-9

Merge Sort-9

Concurrency-9

Doubly-Linked List-8

Brainteaser-8

Probability and Statistics-7

Quickselect-7

Bucket Sort-6

Suffix Array-6

Minimum Spanning Tree-5

Counting Sort-5

Shell-4

Line Sweep-4

Reservoir Sampling-4

Eulerian Circuit-3

Radix Sort-3

Strongly Connected Componen-t2

Rejection Sampling-2

Biconnected Component-1

## Leave a comment below