DSA · Dynamic Programming · #179
Triangle
Module 47 · difficulty 3/5·⏱ 30:00starts on first keystroke
Given a `triangle` array, return the minimum path sum from top to bottom. Each step you may move to an adjacent number on the row below. If you are on index `i` of the current row, you may move to index `i` or `i + 1` on the next row. Implement `function minimumTotal(triangle)` that takes an array of rows (each row an array of integers, where row `r` has `r + 1` elements) and returns the minimum top-to-bottom path sum as a number.
Examples
triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]→11— Path 2 -> 3 -> 5 -> 1 = 11.triangle = [[-10]]→-10— Single element.triangle = [[1],[2,3]]→3— 1 -> 2 = 3.
Constraints
- · 1 <= triangle.length <= 200
- · triangle[0].length == 1
- · triangle[i].length == triangle[i - 1].length + 1
- · -10^4 <= triangle[i][j] <= 10^4
Session phases
A · Clarify
B · Approach
C · Complexity
D · Edges
E · Code
F · Tradeoff
G · Score
Phase A — Clarify
Ask questions about input bounds, types, and edge constraints.
Ask the coach clarifying questions about the problem.
When you've covered this phase, advance to the next.