Cheapest Top-to-Bottom Path in a Triangle

medium dp

Problem

You are given a triangular array where row i has i + 1 entries. Starting at the top, each step moves to one of the two adjacent indices in the row below. Return the minimum total of values along any top-to-bottom path.

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];
}

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