Loading problem...
You are given a rectangular grid of dimensions m × n, where each cell contains a non-negative integer representing the cost to traverse through that cell.
Your objective is to find a path from the top-left corner (position [0,0]) to the bottom-right corner (position [m-1, n-1]) such that the total cumulative cost of all cells visited along the path is minimized.
Movement Constraint: At any given position in the grid, you are only permitted to move in one of two directions:
The cost of a path is defined as the sum of the values of all cells visited during the traversal, including both the starting cell (top-left) and the destination cell (bottom-right).
Return the minimum possible total cost to traverse from the top-left corner to the bottom-right corner of the grid.
grid = [[1,3,1],[1,5,1],[4,2,1]]7The optimal path follows the route: 1 → 3 → 1 → 1 → 1. This traverses through the cells containing values 1, 3, 1, 1, and 1, yielding a total cost of 1 + 3 + 1 + 1 + 1 = 7. Alternative paths such as 1 → 1 → 5 → 1 → 1 (cost = 9) or 1 → 1 → 4 → 2 → 1 (cost = 9) all result in higher costs.
grid = [[1,2,3],[4,5,6]]12The minimum cost path is 1 → 2 → 3 → 6, giving a total cost of 1 + 2 + 3 + 6 = 12. The alternative path 1 → 4 → 5 → 6 yields a cost of 16, which is higher.
grid = [[1,2],[3,4]]7Two possible paths exist: (1) 1 → 2 → 4 with cost 7, and (2) 1 → 3 → 4 with cost 8. The first path yields the minimum cost of 7.
Constraints