~/DHRUVUpskilling
← board/DSA/Dynamic Programming/dsa-dynamic-programming-11
Solved·02 Oct

Triangle

DifficultyMedium
PatternDynamic Programming
TrackDSA
tl;dr

In a right angle triangle you can only move down and down right . Find minimum sum

full write-up

Triangle Minimum Path Sum

Problem Statement

Given a triangle array, return the minimum path sum from the top to the bottom.

At each step, you can move to an adjacent number in the row below. More specifically, if you're at index i in the current row, you can move to either index i or index i + 1 in the next row.

Examples

Example 1

Input: triangle = [[2], [3,4], [6,5,7], [4,1,8,3]]

Output: 11

Explanation: The triangle looks like this:

   2
  3 4
 6 5 7
4 1 8 3

The minimum path sum from top to bottom is 2 + 3 + 5 + 1 = 11.

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⁴ ≤ triangle[i][j] ≤ 10⁴ (this value appeared as "-104...104" in the original text — it most likely means 10⁴, but you may want to double-check the original source)

Solution

Memoization (Top-Down)

We use recursion, starting from the top of the triangle. At each cell, we try moving straight down and diagonally down-right, and take whichever path gives the smaller total sum. We store each cell's result the first time we calculate it, so we never repeat the same work.

  • The base case is the last row: a cell's value there is simply its own number, since there's nowhere left to move.
var minimumTotal = function (triangle) {
    let n = triangle.length;
    let dp = Array.from({ length: n }, () => Array(n).fill(undefined));

    function recurr(i, j, dp) {
        if (i == n - 1) {
            return triangle[i][j];
        }

        if (dp[i][j] !== undefined) {
            return dp[i][j];
        }

        let down = recurr(i + 1, j, dp);
        let diaglonal = recurr(i + 1, j + 1, dp);

        dp[i][j] = triangle[i][j] + Math.min(down, diaglonal);
        return dp[i][j];
    }

    return recurr(0, 0, dp);
};

Tabulation (Bottom-Up)

Instead of starting from the top, we start from the last row, since those cells are our base cases. We then move upward, row by row, calculating the minimum path sum for each cell based on the two cells below it.

var minimumTotal = function (triangle) {
    let n = triangle.length;
    let dp = Array.from({ length: n }, () => Array(n).fill(0));

    for (let col = 0; col < n; col++) {
        dp[n - 1][col] = triangle[n - 1][col];
    }

    for (let i = n - 2; i >= 0; i--) {
        for (let j = 0; j <= i; j++) {

            let down = dp[i + 1][j];
            let downRight = dp[i + 1][j + 1];

            dp[i][j] = triangle[i][j] + Math.min(down, downRight);
        }
    }

    return dp[0][0];
};