Standard Bar Dynamic Programming · 2D DP O(n^2) · O(n)
A warehouse sorter drops parcels down an n x n chute lattice: a parcel in column j lands in column j-1, j, or j+1 of the next level, and every cell it passes charges a handling fee. The floor manager wants the cheapest possible descent fee from the top level to the bottom, so the chute controller must scan all falling trajectories and report the minimal sum.
Input: An n x n matrix matrix of integers, where matrix[i][j] is the fee at level i, column j.
Output: Return the minimum sum of fees over any falling path that starts anywhere on the top row and ends on the bottom row.
1 <= n <= 100-100 <= matrix[i][j] <= 100Input: {"matrix":[[2,1,3],[6,5,4],[7,8,9]]}
Output: 13
Descents 1-4-8 and 1-5-8 both total 13 — the cheapest of all falls.
Input: {"matrix":[[-19,57],[-40,-5]]}
Output: -59
Start at -19, fall straight down to -40 — total -59.