Unique Paths — The One-Way City

Boss 1: The One-Way City

New dungeon, and the biggest one yet. Dungeon 12 taught 1-D dynamic programming: a line of subproblems, each answer built from one or two earlier answers on the same line. Dungeon 16 asks one question, eleven times: what happens when the line becomes a table?

This boss is the gate. It's the gentlest problem in the dungeon on purpose, because it teaches the single move every later boss reuses: a cell is a combination of neighbors you've already solved. Learn to read a 2-D table as "smaller solved problems feeding a bigger one" and the next ten bosses are variations on today.

The story

You're a courier in the One-Way City. Urban planning here was done by someone with strong opinions: every street runs one-way, either east or south. No turning back north, no sneaking west.

The depot sits at the northwest corner. Today's drop-off is at the southeast corner. Your dispatcher, watching you trace routes on the wall map, asks the annoying question:

"How many different legal routes are there, anyway?"

For a tiny 2-block by 2-block map you can count on fingers. For the real city, a 3-avenue by 4-street grid, it's already slippery. For the metro area? You need something better than fingers.

The problem, dressed up properly

There is a robot on an m x n grid, starting at the top-left corner. The robot can only move right or down. Return the number of possible unique paths to reach the bottom-right corner.

LeetCode 62, "Unique Paths". The classic opener for grid DP, and the cleanest possible statement of "count the ways" on two axes.

The naive attempt

Stand at an intersection and branch:

def unique_paths(m, n):
    def paths(r, c):
        if r == m - 1 or c == n - 1:
            return 1                      # last row or column: one straight shot left
        return paths(r + 1, c) + paths(r, c + 1)
    return paths(0, 0)

Correct, and doomed. Every call spawns two more, so the tree has roughly 2^(m+n) nodes. But the real crime is repetition. From the depot, "east then south" and "south then east" both land on intersection (1, 1), and the recursion happily recomputes everything below (1, 1) from scratch, twice. Deeper cells get recomputed hundreds of times.

Dungeon 12 flashback: Climbing Stairs had exactly this disease, climb(n) = climb(n-1) + climb(n-2) recomputing the same floor over and over. The cure there was a table with one row. The cure here is a table with rows and columns, because the state has two coordinates now, not one.

The weapon: the delivery ledger

Flip the question. Instead of "how many routes leave the depot?", ask each intersection: "how many routes arrive here?"

Every route into intersection (r, c) took its final step either from the intersection above or the one to the left. Those are the only streets pointing in. So:

• dp[r][c] = dp[r-1][c] + dp[r][c-1]
• Top row and left column are all 1: with one-way streets, there's exactly one way to hug an edge.

Fill row by row, left to right, and every cell you compute uses two cells that are already final. No recursion, no recomputation, each intersection solved exactly once.

And here's the space upgrade. While filling row r, you only ever look at row r-1 and the cell just written. So keep one row. Before updating, dp[j] still holds the value from the row above; dp[j-1] already holds the fresh value to the left. One line does both jobs:

def unique_paths(m: int, n: int) -> int:
    dp = [1] * n                      # first row: all ones
    for _ in range(1, m):             # each remaining row
        for j in range(1, n):         # left to right
            dp[j] += dp[j - 1]        # above (old dp[j]) + left (new dp[j-1])
    return dp[-1]

One honest aside: mathematicians teleport past this boss. Every route is m+n-2 moves, and choosing which m-1 of them go south fixes the route, so the answer is C(m+n-2, m-1), one binomial and done. Take the teleport in an interview if it's offered. But the table is the lesson: the closed form dies the moment Boss 3 drops an obstacle on the grid, and the DP table shrugs and keeps filling.

Watching it work

The dispatcher's map: 3 avenues by 4 streets, so a 3x4 grid. First row and column are 1s, then each cell is above plus left:

row 0:   1   1   1   1     (hug the north edge)
row 1:   1   2   3   4     (1+1=2, 2+1=3, 3+1=4)
row 2:   1   3   6  10     (2+1=3, 3+3=6, 4+6=10)

answer: 10 distinct routes

Read cell (2, 2) = 6 out loud: six routes reach it, three arriving from above and three from the left. The table isn't storing paths, it's storing counts of solved subproblems, and the bottom-right sums the whole city's structure into one number.

Now the same map with the rolling row, dp starting as [1, 1, 1, 1]:

after row 1:   [1, 2, 3, 4]
after row 2:   [1, 3, 6, 10]

dp[-1] = 10 ✓

Same numbers, one row of memory. Each dp[j] += dp[j-1] overwrites "the cell above me" with "me".

Gotchas

1. Initializing the first row and column to 0. The edges are the base case and they are all 1, not 0. There is exactly one way to travel a one-way edge street: straight. Zero the edges and the entire table collapses to zeros, since every cell is a sum of its ancestors.

2. Rolling to 1-D with the wrong sweep direction. dp[j] += dp[j-1] only works left to right, because it needs dp[j-1] to be this row's fresh value while dp[j] is still last row's. Sweep right to left and you add stale left-values, quietly producing wrong counts with no crash to warn you. When in doubt, ask of each read: "should this be old or new?"

3. Mixing up m and n. m is rows, n is columns, and this problem is symmetric so unique_paths(3, 7) equals unique_paths(7, 3), which hides the bug. Swap them in a problem that isn't symmetric (most of this dungeon) and you'll index out of bounds or get garbage. Pick a convention, r for rows against m, j for columns against n, and never bend it.

4. Off-by-one on what the grid counts. An m x n grid has m * n intersections and the trip takes m + n - 2 moves, not m + n. In the recursion, the base case is r == m - 1 or c == n - 1, the last row or column, where only one straight route remains. Writing r == m walks off the map.

Complexity

Every intersection computed once, from two lookups.

Time: O(m·n). Space: O(n) with the rolling row, O(m·n) if you keep the full table (and for debugging, honestly, keep it, seeing the table is the point).

Boss down

The dispatcher gets the answer, 10 routes for the wall map, and you get something better: the shape of the whole dungeon. Climbing Stairs was a hallway where each step summed the two behind it. Give the hallway a second axis and each cell sums the two neighbors behind it, above and left. Same idea, one dimension richer.

The gate is open. Next up, Boss 2: Longest Common Subsequence — The Two Diaries. Two old diaries describe the same trip, and you want the longest sequence of moments they agree on, in order. Two strings enter the table this time, one along each axis, and each cell compares a prefix of both. The grid stops being a map and becomes a comparison, and that's the version of 2-D DP interviews love most. Bring the ledger.