Path Counting on a Grid
Sum paths from corner to corner.
Path Counting on a Grid is a free Coding Interview Prep lesson on CoddyKit — lesson 1 of 4. You can read the complete lesson below for free — then practise it hands-on in the browser with a built-in code editor and a 24/7 AI tutor. It is part of the Coding Interview Prep learning path, one of 4 lessons in the course, and your progress syncs across the web and the CoddyKit app.
The Classic Grid Problem
You start at the top-left of a grid and want the bottom-right. Each step moves right or down. How many distinct paths exist?
Why DP Fits
Every cell can be reached from the cell above or the cell to its left. That overlap is exactly why this is a DP problem.
Define the State
Let dp[i][j] be the number of ways to reach cell (i, j) from the start. Naming the state clearly is half the battle.
The Transition
You only arrive from above or from the left, so the count is their sum. This is the transition that drives the whole table.
dp[i][j] = dp[i-1][j] + dp[i][j-1]The Base Case
The start cell has exactly one way to reach it: do nothing. So dp[0][0] is 1 before you fill anything else.
dp[0][0] = 1Edges Have One Path
Cells in the top row or left column have a single straight route. Their count is always 1, since one neighbor is off the grid.
Build the Table
Make an m by n table filled with zeros. Sizing it up front keeps your indexing clean and avoids surprises.
dp = [[0] * n for _ in range(m)]Fill in Reading Order
Loop rows then columns, top to bottom and left to right. This order guarantees both neighbors are ready before you use them.
for i in range(m):
for j in range(n):
...The Answer Cell
After filling, the path count lives in the last cell. The answer is dp[m-1][n-1], the bottom-right corner.
answer = dp[m-1][n-1]Save Memory with One Row
Each row only needs the row above, so you can keep a single row and update it in place. That cuts memory to O(n).
row[j] += row[j-1]The Math Shortcut
With no blocks, the answer is a binomial coefficient: choose which of the total steps go down. DP still wins once obstacles appear.
Quick Check
You are filling dp[i][j] for an open inner cell. Which formula is right?
Recap: Path Counting
Define dp as paths to a cell, set dp[0][0] to 1, and add the cell above plus the cell left. The corner holds your answer. 🧭
Frequently asked questions
Is the “Path Counting on a Grid” lesson free?
Yes — the full text of “Path Counting on a Grid” is free to read here on the web, and the Coding Interview Prep course includes 4 lessons in total. To practise it interactively (a built-in code editor and a 24/7 AI tutor) and unlock the rest of the Coding Interview Prep course, upgrade to CoddyKit PRO.
What will I learn in “Path Counting on a Grid”?
Sum paths from corner to corner. You practise Coding Interview Prep with hands-on code you run directly in the browser, and a 24/7 AI tutor answers your questions as you work through the lesson.
Do I need any experience to start Coding Interview Prep?
No prior experience is required. Coding Interview Prep on CoddyKit is structured for beginners through advanced learners; this is — lesson 1 of 4, so you can start here or from the beginning and move at your own pace.
How long does the “Path Counting on a Grid” lesson take?
Most CoddyKit lessons take about 5–10 minutes. Each one is bite-sized and interactive, so you make steady progress and pick up exactly where you left off across the web and the app.
Can I write and run code in this Coding Interview Prep lesson?
Yes. Every Coding Interview Prep lesson includes a built-in code editor, so you write and run real code right in your browser and get instant AI feedback — no local setup required.
All lessons in this course
- Path Counting on a Grid
- Minimum Path Sum with Obstacles
- Longest Common Subsequence
- Edit Distance Step by Step