Standard Bar Dynamic Programming · 2D DP O(n^2) · O(n)
A terminal's wayfinding map is a triangular lattice of moving walkways: the apex sits at the top, and each walkway descends to one of two adjacent nodes on the row below. Every walkway posts a queue-time toll. Operations wants the least-cost descent from apex to bottom row, so the kiosk must evaluate the toll-minimal chain before suggesting a route.
Input: A list triangle of rows, where row i has i+1 integers and triangle[i][j] is the toll at that node.
Output: Return the minimum sum of tolls over a top-to-bottom chain of adjacent nodes.
1 <= len(triangle) <= 200-10^4 <= triangle[i][j] <= 10^4Input: {"triangle":[[2],[3,4],[6,5,7],[4,1,8,3]]}
Output: 11
Chain 2, 3, 5, 1 — total 11.
Input: {"triangle":[[-10]]}
Output: -10
A one-row triangle's best chain is its only node.