Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

Practice › Dynamic Programming

Triangle Minimum Path Sum

Medium · Dynamic Programming · Asked at Amazon, Microsoft, Apple, Bloomberg

Row i of the triangle has i numbers. Start at the top and move to an adjacent number in the row below (index j → j or j + 1). Print the minimum sum of a path from the top to the bottom row.

Input

First line: n (number of rows). Next n lines: row i has i integers.

Output

The minimum path sum.

Constraints

Work bottom-up: best[j] = row[j] + min(best[j], best[j+1]). The top cell ends up holding the answer.

Example 1

Input

4
2
3 4
6 5 7
4 1 8 3

Output

11

Example 2

Input

1
-10

Output

-10

Hints

  1. Top-down needs care at the edges of each row; bottom-up does not.
  2. Start with the last row. For each row above, best[j] = row[j] + min(best[j], best[j+1]).

Approach

Let best be the minimum sums from the current row down to the bottom, starting with the last row itself. Moving up one row, the path from (i, j) continues to (i+1, j) or (i+1, j+1), so best[j] = row[j] + min(best[j], best[j+1]) (updating left to right reuses the array safely). After the top row, best[0] is the answer.

Complexity: O(n²) time · O(n) space

Solution

C++ solution

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<vector<long long>> t(n);
    for (int i = 0; i < n; i++) {
        t[i].resize(i + 1);
        for (auto &x : t[i]) cin >> x;
    }
    vector<long long> best = t[n - 1];
    for (int i = n - 2; i >= 0; i--)
        for (int j = 0; j <= i; j++) best[j] = t[i][j] + min(best[j], best[j + 1]);
    cout << best[0] << "\n";
    return 0;
}

Python solution

import sys

data = list(map(int, sys.stdin.read().split()))
n, p = data[0], 1
t = []
for i in range(n):
    t.append(data[p : p + i + 1])
    p += i + 1
best = t[-1][:]
for i in range(n - 2, -1, -1):
    for j in range(i + 1):
        best[j] = t[i][j] + min(best[j], best[j + 1])
print(best[0])

Java solution

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        long[][] t = new long[n][];
        for (int i = 0; i < n; i++) {
            t[i] = new long[i + 1];
            for (int j = 0; j <= i; j++) t[i][j] = sc.nextLong();
        }
        long[] best = t[n - 1].clone();
        for (int i = n - 2; i >= 0; i--)
            for (int j = 0; j <= i; j++) best[j] = t[i][j] + Math.min(best[j], best[j + 1]);
        System.out.println(best[0]);
    }
}

Solve Triangle Minimum Path Sum online · All practice problems