Abstract / Summary

Find the lowest total cost to move from the top left to the bottom right of a grid by moving only right or down.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 68% (60k+ submissions).

Typical patterns to solve this problem:

• Array
• Dynamic Programming
• Matrix

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided Solution class implements a dynamic-programming algorithm that computes the minimum cost of a path from the top row to the bottom row of a rectangular grid. Each cell in the grid contributes its own value to the total cost, and moving from a cell in one row to a cell in the next row incurs an additional cost taken from the moveCost matrix. The algorithm proceeds row by row, maintaining the cheapest cost to reach each column of the current row, and finally returns the smallest accumulated cost among the cells of the last row.

Initialization of Dimensions and First Row

height = len(grid)
width  = len(grid[0])

previous = grid[0]   # first row

The code extracts the number of rows (height) and columns (width). It then seeds the dynamic-programming state with the values of the first row, because any path must start in one of those cells and the cost at that point is simply the cell’s own value.

Iterative Row-by-Row Transition

The core of the algorithm is a loop that processes each pair of consecutive rows.

for y in range(height - 1):
    next = [ +inf ] * width

For each row index y (except the last), a new list next is allocated and filled with positive infinity. This list will hold the minimum cost to reach each column of the row y + 1. Using a sentinel large value ensures that any real cost will replace it during the minimisation step.

Exploration of All Column Pairs

Inside the outer loop, two nested loops enumerate every possible transition from a column x in the current row to a column x2 in the next row.

for x in range(width):
    id = grid[y][x]
    for x2 in range(width):
        # try all paths between two consecutive rows
        cost = previous[x] + moveCost[id][x2] + grid[y + 1][x2]
        next[x2] = min(next[x2], cost)

The variable id captures the value stored in the current cell, which serves as an index into the moveCost matrix. The inner expression computes the total cost of a candidate path:

1. previous[x] - the cheapest cost to reach column x of the current row.
2. moveCost[id][x2] - the cost of moving from the current cell (identified by id) to column x2 of the next row.
3. grid[y + 1][x2] - the intrinsic cost of the destination cell.

The min operation updates next[x2] with the smallest cost found for that destination column. By iterating over all source columns, the algorithm guarantees that every feasible transition is examined.

Advancement of the DP State

After all transitions for a given row pair have been evaluated, the previous reference is updated to point to the freshly computed next list.

previous = next

This step discards the costs of the older row and prepares the algorithm for the next iteration, ensuring that memory usage stays bounded by two rows.

Final Selection of Minimum Path Cost

When the loop finishes, previous contains the minimum accumulated cost for each column of the bottom row. The answer is the smallest entry among them.

return min(previous)

Because the algorithm has already accounted for the cost of the last row’s cells during the last transition, no additional adjustment is required.

Edge Cases Handled

The implementation gracefully handles grids with a single row. In that situation height - 1 evaluates to zero, the outer loop body never executes, and the method directly returns the minimum value of the first row, which is the correct answer because no moves are needed.

When the grid contains only one column, the inner loop over x2 iterates once, and the transition cost reduces to the sum of the accumulated cost, the move cost for the single column, and the next cell’s value. The algorithm still explores the single possible path and yields the correct total.

The use of +inf as the initial value for the next list guarantees that even if all candidate costs are large, the minimisation step will correctly replace the placeholder with a finite value. This prevents accidental retention of the sentinel value in the final result.

Performance Optimisations Observed

The code confines its auxiliary storage to two one-dimensional arrays of length equal to the grid width. By reusing these arrays row after row, the memory footprint remains linear in the number of columns, independent of the number of rows.

The inner computation avoids any unnecessary data structures; it directly accesses the required elements from grid, moveCost, and the DP arrays. This tight loop benefits from CPU cache locality because the accesses to moveCost[id] and grid[y + 1] are sequential across columns.

Pre-computing previous[x] once per outer iteration and reusing it for all inner transitions eliminates redundant lookups. The algorithm also leverages Python’s built-in min function, which is implemented in C and therefore faster than a manual conditional assignment.

Overall, the design balances clarity with efficiency, delivering a solution that scales well with typical input sizes while keeping the implementation straightforward.

Imagine building a path across a big grid of colored tiles. Every tile has a special secret number on it. Starting at the very top row, the goal is to make it all the way to the bottom row by jumping between tiles.

Each time a jump is made from one tile to the next row, there is a tiny toll to pay, which is just another secret number. To find the cheapest way to reach the bottom, the code starts by looking at the first row of tiles. Then, it moves down to the next row one step at a time.

For every single tile in the row being jumped from, the code checks every possible tile in the row below. It adds up the cost of standing on the current tile, the cost of moving to the new tile, and the value of the new tile itself. As it looks at all these paths, it only keeps track of the smallest total cost found for each tile in the new row.

This process repeats row by row, like climbing down a ladder where each rung is a new row of tiles. Once the bottom row is reached, the code looks at all the final tiles and picks the one with the lowest total cost. It is just like finding the shortest path through a maze by keeping track of the smallest numbers found at every turn.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: polynomial
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster		Python	Java	C++			TS
	WalkCCC		Python	Java	C++
	leetcode.ca		Python	Java	C++	Go	Rust	TS
	Progiez		Python	Java	C++
github	charles-wangkai			Java
	everthis	JS
	fsq				C++
	JoshCrozier	JS
	lkwq007		Python
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python, Rust, TypeScript
Progiez	C++, Java, Python
charles-wangkai	Java
everthis	JavaScript
fsq	C++
JoshCrozier	JavaScript
lkwq007	Python

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality