Triangle
Minimum top-to-bottom path sum in a triangle — in-place bottom-up DP.
2 min read
Problem#
Minimum path sum from top to bottom of a triangle. Each step moves to one of the two adjacent cells of the next row.
Examples#
[[2],[3,4],[6,5,7],[4,1,8,3]]→11
Constraints#
1 <= n <= 200.
Approach#
Bottom-up: triangle[i][j] += min(triangle[i+1][j], triangle[i+1][j+1]). Top of the modified triangle holds the answer.
Solution#
class Solution {public: int minimumTotal(vector<vector<int>>& t) { for (int i = t.size() - 2; i >= 0; --i) for (int j = 0; j <= i; ++j) t[i][j] += min(t[i + 1][j], t[i + 1][j + 1]); return t[0][0]; }};func minimumTotal(t [][]int) int { for i := len(t) - 2; i >= 0; i-- { for j := 0; j <= i; j++ { a, b := t[i+1][j], t[i+1][j+1] if a < b { t[i][j] += a } else { t[i][j] += b } } } return t[0][0]}from typing import List
class Solution: def minimumTotal(self, t: List[List[int]]) -> int: for i in range(len(t) - 2, -1, -1): for j in range(i + 1): t[i][j] += min(t[i + 1][j], t[i + 1][j + 1]) return t[0][0]var minimumTotal = function(t) { for (let i = t.length - 2; i >= 0; i--) { for (let j = 0; j <= i; j++) { t[i][j] += Math.min(t[i + 1][j], t[i + 1][j + 1]); } } return t[0][0];};class Solution { public int minimumTotal(List<List<Integer>> t) { for (int i = t.size() - 2; i >= 0; i--) { for (int j = 0; j <= i; j++) { int cur = t.get(i).get(j); int next = Math.min(t.get(i + 1).get(j), t.get(i + 1).get(j + 1)); t.get(i).set(j, cur + next); } } return t.get(0).get(0); }}function minimumTotal(t: number[][]): number { for (let i = t.length - 2; i >= 0; i--) { for (let j = 0; j <= i; j++) { t[i][j] += Math.min(t[i + 1][j], t[i + 1][j + 1]); } } return t[0][0];}Editorial#
In-place bottom-up avoids any extra storage. Going bottom-up sidesteps the “I don’t know future minimums” problem of top-down — every cell’s children are already finalized.
Complexity#
- Time: O(n²).
- Space: O(1).
Concept revision#
Related#