Image Pyramid Cost
A photo-editor app pre-computes a multi-resolution pyramid of every image so the viewer can scrub between zoom levels smoothly. Generating each tile has a cost (in CPU ms) given by a grid. The pipeline walks from the top-left tile (highest resolution) to the bottom-right tile (thumbnail), and at each step can move only right or down. Find the minimum total cost path.
Problem
Given an m × n grid of non-negative integers grid where grid[i][j] is the cost of generating tile (i, j), return the minimum total cost to travel from grid[0][0] to grid[m−1][n−1] moving only right (i, j+1) or down (i+1, j).
Input
Integers m and n (1 ≤ m, n ≤ 500) and the grid (0 ≤ grid[i][j] ≤ 10^4).
Output
A single integer — the minimum cumulative cost of any valid path.
Constraints
- 1 ≤ m, n ≤ 500
- 0 ≤ grid[i][j] ≤ 10,000
- Movement restricted to right or down
- The cost of the starting and ending tiles are included
Examples
Example 1
Input
grid = [[1,3,1],[1,5,1],[4,2,1]]
Output
7
Path 1→3→1→1→1 sums to 7. No path is cheaper given the right/down restriction.
Example 2
Input
grid = [[5]]
Output
5
Single cell — just the cell's cost.