Standard Bar Dynamic Programming · 2D DP O(m*n) · O(n)
An assembly robot traces a trace from the top-left pad of an m x n circuit board to the bottom-right pad, moving only right or down. Every pad levies a solder-time toll recorded in a grid, and the plant wants each trace to cost as little as possible. Program the planner to report the cheapest achievable toll total across any legal route.
Input: An m x n matrix grid of non-negative integers, where grid[i][j] is the toll at cell (i, j).
Output: Return the minimum possible sum of tolls along a right/down path from the top-left to the bottom-right cell.
1 <= m, n <= 2000 <= grid[i][j] <= 200Input: {"grid":[[1,3,1],[1,5,1],[4,2,1]]}
Output: 7
Route 1, 3, 1, 1, 1 hugs the top edge then drops — total 7.
Input: {"grid":[[1,2,3],[4,5,6]]}
Output: 12
Straight across the top row: 1 + 2 + 3 + 6 = 12.