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
- 1 ≤ n ≤ 1000
- -10^4 ≤ values ≤ 10^4
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
- Top-down needs care at the edges of each row; bottom-up does not.
- 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