hardDynamic Programming 2DPure DSA~30 min
Warehouse Grid Min Path
A picking robot crosses a warehouse grid from the top-left bay to the bottom-right shipping dock, moving only right or down. Each cell has a traversal cost (congestion). Find the minimum total cost path.
Problem
Given an r×c grid of non-negative costs, return the minimum sum of costs along a path from cell (0,0) to (r-1,c-1) moving only right or down.
Input
A grid with r rows and c columns (1 ≤ r, c ≤ 1000), each cost in [0, 10^4].
Output
A single integer — the minimum path cost.
Constraints
- 1 ≤ r, c ≤ 1000
- 0 ≤ cost ≤ 10,000
- Moves restricted to right and down
Examples
Example 1
Input
grid = [[1,3,1],[1,5,1],[4,2,1]]
Output
7
Path 1→3→1→1→1 (right,right,down,down) sums to 7, the minimum.
Example 2
Input
grid = [[1,2],[1,1]]
Output
3
Down then right (1→1→1 = 3) beats right then down (1→2→1 = 4).