# Find minimum path sum in a triangle-shaped matrix | Techie Delight Given a right-angled triangle-shaped matrix, find the shortest path sum from the top element to any element in the last row of the matrix.

We can only move down from the present cell at any given time. Hence, the legal movements from cell `(x,y)` are either `(x+1,y)` or `(x+1,y+1)`. For example,

Input: mat = [
,
[1, 3],
[1, 2, 1],
[8, 4, 5, 1]
]

Output: 9

Explanation: The minimum path is [4, 3, 1, 1] having sum 9.

A closer look reveals that this problem may be recursively divided into smaller subproblems, with each problem being repeated numerous times. Dynamic programming can be used to solve problems with optimal substructure and overlapping subproblems.

The idea is to save subproblem solutions rather than repeatedly computing them. We begin by building a 2D array `T[][]` to record the solutions to the subproblems, where `T[i][j]` will hold the minimum sum path for the ith row and jth column. Here, `T[i][j]` would equal the total of the current cell and the lower of its bottom and bottom-right cell path sums. This results in the following recurrence:

T[i][j] = mat[i][j] + min(T[i+1][j], T[i+1][j+1])

For instance, using the recurrence described above, the matrix to the left will produce the table to the right. The shortest path has the total `9` and is `[4, 3, 1, 1]`.

                         [9, 0, 0, 0]
[1, 3]            —>        [6, 5, 0, 0]
[1, 2, 1]                   [5, 6, 2, 0]
[8, 4, 5, 1]                [8, 4, 5, 1]

The implementation can be seen below in C++, Java, and Python:

Output:

9

Output:

9

## Python

Output:

9

The time complexity of the above solution is O(N × N) and requires O(N × N) extra space, where `N` is the number of rows in the matrix.

Take note of the bottom-up filling of the `T[][]` table. As we are always reading from the subsequent row of the current row, the space complexity of the solution can be reduced to O(N). The space-optimized algorithm can be implemented as follows in C++, Java, and Python:

Output:

9

Output:

9

## Python

Output:

9

The time complexity of the above solution is O(N × N) and requires O(N) extra space, where `N` is the number of rows in the matrix.