Triangle

Leetcode Problem 120: Triangle

Problem Summary

Given a triangle array, where row i contains i + 1 entries, return the minimum path sum from the top to the bottom. At each step, from index j on the current row you may move to index j or index j + 1 on the row below. The triangle has between 1 and 200 rows, and each value is between -10^4 and 10^4. A well-known follow-up asks to solve it using only O(n) extra space, where n is the number of rows.

Techniques

• Array
• Dynamic Programming

Solution

function minimumTotal(triangle: number[][]): number {
    const m = triangle.length;
    const dp = triangle.map((row) => [...row]);

    for (let i = m - 2; i >= 0; i--) {
        for (let j = 0; j <= i; j++) {
            dp[i][j] = triangle[i][j] + Math.min(dp[i + 1][j], dp[i + 1][j + 1]);
        }
    }

    return dp[0][0];
}