Triangle

medium dp

Problem

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.

Inputtriangle = [[2],[3,4],[6,5,7],[4,1,8,3]]

Output11

Walk bottom-up. dp[j] in the working row holds the cheapest cost from triangle[i][j] to the bottom; replace it with triangle[i][j] + min(dp[j], dp[j+1]).

triangle (rows separated by ;)

def minimum_total(triangle):
    dp = list(triangle[-1])
    for i in range(len(triangle) - 2, -1, -1):
        for j in range(i + 1):
            dp[j] = triangle[i][j] + min(dp[j], dp[j + 1])
    return dp[0]

function minimumTotal(triangle) {
  const dp = triangle[triangle.length - 1].slice();
  for (let i = triangle.length - 2; i >= 0; i--) {
    for (let j = 0; j <= i; j++) {
      dp[j] = triangle[i][j] + Math.min(dp[j], dp[j + 1]);
    }
  }
  return dp[0];
}

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

int minimumTotal(vector<vector<int>>& triangle) {
    int n = triangle.size();
    vector<int> dp = triangle[n - 1];
    for (int i = n - 2; i >= 0; i--) {
        for (int j = 0; j <= i; j++) {
            dp[j] = triangle[i][j] + min(dp[j], dp[j + 1]);
        }
    }
    return dp[0];
}

Explanation

We want the cheapest path from the top of the triangle to the bottom, where each step moves to one of the two numbers directly below. The neat trick is to solve it bottom-up instead of top-down.

We keep a single array dp that starts as a copy of the last row. At that point dp[j] is just the cost of standing on the bottom cell j — there is nowhere left to go.

Then we walk up one row at a time. For a cell at row i, column j, the cheapest way down is the cell's own value plus the smaller of its two children: dp[j] = triangle[i][j] + min(dp[j], dp[j+1]). Because dp currently holds the row below, those two children are exactly dp[j] and dp[j+1].

Reusing one array works because once we overwrite dp[j] for the new row, we no longer need the old value at that slot for anything to its right.

Example: [[2],[3,4],[6,5,7],[4,1,8,3]]. Building up gives the path 2 → 3 → 5 → 1 with total 11, which ends up in dp[0], the answer.

Time: O(n²) Space: O(n)