209. Minimum Cost Path in a Grid

Given a grid of costs, find the minimum total cost to travel from the top-left cell to the bottom-right cell, where a move can go right, down, or diagonally down-right, and the cost of a path is the sum of the costs of every cell visited, including the start and end.

Input: The first line contains two integers rows and cols. Each of the next rows lines contains cols space-separated integers, the grid of cell costs. Output: Print a single integer - the minimum total cost of a path from the top-left to the bottom-right cell.

1 <= rows, cols <= 1000

Treating out-of-grid positions as infinitely costly (rather than 0 or some other sentinel) correctly ensures the min() naturally ignores nonexistent predecessors at the grid's edges and corners.

Find the minimum total cost to travel from a grid's top-left to bottom-right, moving right, down, or diagonally down-right. Brute force: Try every possible path from top-left to bottom-right directly and compute each one's cost - this is exponential (combinatorially many paths), impractical for large grids. Optimised: Since the minimum cost to reach any cell only depends on the minimum costs to reach its three possible predecessor cells (up, left, diagonal-up-left), building the table left-to-right, top-to-bottom ensures every needed predecessor value is already computed exactly once.

Use the same recursive structure as the brute-force approach, but cache the minimum cost computed for each cell the first time it's reached and reuse it on subsequent calls instead of recomputing it, using an array of size rows*cols as a memo table. Since every cell's minimum cost only needs to be computed once, this collapses the exponential brute-force recursion down to one computation per cell. Time: O(rows * cols) Space: O(rows * cols)

Fill the DP table iteratively from the top-left cell outward in row-major order, where each cell's minimum cost is its own cost plus the minimum of the cell above, the cell to the left, and the cell diagonally above-left, since those are exactly the cells that could have moved into it. Because each row's computation only depends on the current and previous row, the DP table can be shrunk to a single rolling 1D array of size cols, and the iterative order avoids any recursion call overhead or stack-depth risk for grids as large as 1000x1000. Time: O(rows * cols) Space: O(cols)

From every cell, recursively try all three allowed moves (right, down, diagonal) and recursively compute the minimum cost path to the destination from each resulting cell, adding the current cell's cost, then take the minimum of the three recursive results. This directly explores every possible path from top-left to bottom-right, but the same sub-cells get recomputed many times from different paths, so the total work grows exponentially with the grid's dimensions. Time: O(3^(rows+cols)) Space: O(rows+cols)

1. dp[i][j] = minimum cost to reach cell (i,j) from (0,0). 2. dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) - treating any position outside the grid as infinitely costly (unreachable). 3. The answer is dp[rows-1][cols-1].

Time: O(rows*cols) - filling the DP table, one cell at a time. Space: O(rows*cols) for the full table (reducible to O(cols) with a rolling 1D array).

Test a 1x1 grid (the cost is just that single cell), a single row or single column grid, and rows/cols at the upper bound of 1000.

Be ready to contrast this with the more common 'right or down only' grid path problems - the added DIAGONAL move option here just adds one more term to the min() comparison, a small but easy detail to miss if working from memory of the simpler variant.