Abstract / Summary

A robot moves from the top left to the bottom right of a grid moving only right or down how many different routes can it take

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 67% (4+ million submissions).

Typical patterns to solve this problem:

• Combinatorics
• Dynamic Programming
• Math

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 implementation computes the number of distinct paths from the top-left corner to the bottom-right corner of an m-by-n grid, moving only down or right. It builds a two-dimensional dynamic programming table, initializes the starting cell, propagates path counts across the grid, and finally returns the value stored in the destination cell.

Key Steps

The algorithm proceeds through a clear sequence of operations.

The first step creates a matrix named board that will hold the cumulative path counts. The matrix is sized to m rows and n columns using resize calls.

vector<vector<int>> board;
board.resize(m);
for (auto& b : board)
    b.resize(n);

Next, the starting position at the top-left corner is seeded with a count of one, representing the single way to be at the origin.

board[0][0] = 1;

The core of the solution is a double loop that iterates over every cell in row-major order. For each cell, the algorithm adds the number of ways to reach the cell directly above (if such a cell exists) and the number of ways to reach the cell directly to the left (if such a cell exists). This accumulation builds the total number of ways to arrive at the current cell.

for (int x = 0; x < m; x++)
    for (int y = 0; y < n; y++)
    {
        if (x > 0)
            board[x][y] += board[x-1][y];
        if (y > 0)
            board[x][y] += board[x][y-1];
    }

Finally, the value stored in the bottom-right cell, board[m-1][n-1], is returned as the answer.

return board[m-1][n-1];

Edge Cases Handled

When either m or n equals one, the grid collapses to a single row or a single column. The loops still execute, but the conditional checks if (x > 0) and if (y > 0) prevent out-of-bounds accesses. In a one-row grid, the x > 0 condition never holds, so each cell accumulates only the value from its left neighbor, correctly yielding a single path. Similarly, in a one-column grid, only the x > 0 branch contributes, also resulting in a single path.

The initialization of board[0][0] to one ensures that even the smallest grid (1 × 1) returns a count of one, representing the trivial path that starts and ends at the same cell.

Performance Optimizations

The implementation allocates the DP table once and reuses it throughout the computation, avoiding repeated memory allocations inside the loops. By resizing each row after the outer resize(m), the code guarantees contiguous storage for each inner vector, which improves cache locality when accessing board[x][y].

The nested loops iterate in a straightforward row-major order, allowing the processor to prefetch successive memory locations efficiently. The conditional checks guard against unnecessary additions for the first row and first column, eliminating redundant operations.

Because the algorithm updates each cell exactly once, the overall work scales linearly with the number of cells in the grid, making the approach suitable for moderate grid sizes without incurring extra overhead from recursion or auxiliary data structures.

Concluding Remarks

The solution follows a classic dynamic programming pattern, translating the combinatorial recurrence into an iterative table fill. It correctly addresses boundary conditions, leverages contiguous memory layout for speed, and maintains a clean, readable structure that aligns with typical C++ idioms for matrix manipulation.

Imagine you have a big square grid made of many little boxes on the floor, and you want to walk from the very top corner to the very bottom corner. There are many different paths you could take. To figure out how many ways there are, the computer builds a special map where each box remembers how many ways you can get there.

First, the computer creates a grid of boxes that is exactly as long and as wide as the path you want to walk. At the very start, it places a number one because there is only one way to be at the beginning.

Then, the computer goes through every single box one by one. For any box, it looks at the box just above it and the box just to the left of it. It adds together the numbers written in those two neighbors and writes that new sum in the current box. This is like saying that if you can get to the top neighbor in five ways and the left neighbor in three ways, then you have eight different ways to reach the current spot.

By the time the computer fills in every box all the way to the end of the room, the last box holds the answer for how many total paths exist to reach that corner.

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	C++	Python	Java								TS
	WalkCCC	C++	Python	Java
	leetcode.ca	C++	Python	Java			Rust	JS			Go	TS
	LeetcodeHelp	C++	Python	Java
	MemoryLimitExceeded	C++	Python
	Progiez	C++	Python	Java
github	aylei						Rust
	begeekmyfriend					C
	BigEggStudy				C#
	black-shadows	C++
	chandansgowda		Python
	charles-wangkai			Java
	chenyanzhe	C++
	everthis							JS
	fartem								Ruby
	FelixFan1122				C#
	fengvyi	C++
	fpdjsns	C++
	gaosq0604		Python
	Garvit244		Python
	halfrost										Go
	haoel	C++
	JoshCrozier							JS
	keineahnung2345	C++
	Krazune			Java
	lennylxx					C
	linouk23	C++
	lkwq007		Python
	luangong	C++
	MacJim	C++
	qiyuangong		Python
	ruoru						Rust
	shreymehul				C#
	suxrobGM				C#
	varunu28			Java
	vli02					C
	vthwang			Java
	XiaotaoGuo	C++
	yuanliu666									Kotlin
	zfang399	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, JavaScript, Python, Rust, TypeScript
LeetcodeHelp	C++, Java, Python
MemoryLimitExceeded	Python, C++
Progiez	C++, Java, Python
aylei	Rust
begeekmyfriend	C
BigEggStudy	C#
black-shadows	C++, C++
chandansgowda	Python
charles-wangkai	Java
chenyanzhe	C++
everthis	JavaScript
fartem	Ruby
FelixFan1122	C#
fengvyi	C++
fpdjsns	C++
gaosq0604	Python
Garvit244	Python
halfrost	Go
haoel	C++
JoshCrozier	JavaScript
keineahnung2345	C++
Krazune	Java
lennylxx	C
linouk23	C++
lkwq007	Python
luangong	C++
MacJim	C++
qiyuangong	Python
ruoru	Rust
shreymehul	C#
suxrobGM	C#
varunu28	Java
vli02	C
vthwang	Java
XiaotaoGuo	C++
yuanliu666	Kotlin
zfang399	C++

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