Intro to Dynamic Programming & Graphs (conceptual)

Today we meet two big ideas: Dynamic Programming (DP) is about remembering the answers to subproblems so we never recompute them, and Graphs are about modeling relationships between things. Both topics have well-worn recipes — the same classic problems show up from textbooks to interview rooms. Important warning: this is exactly the topic where AI most often gives answers that “look right but are subtly wrong,” because code with a slightly wrong recurrence, or a graph traversal missing a visited set, still runs and produces a plausible-looking answer on small examples every time. So always verify — “it ran” is not the bar.

Dynamic Programming

Picture yourself solving a complicated arithmetic problem and jotting down intermediate results on scratch paper — if you hit the same sub-calculation again later, you just glance at the scratch paper instead of recomputing it from scratch. That is the heart of Dynamic Programming (DP): a technique that breaks a big problem into smaller subproblems and remembers their answers so they are never recomputed.

A problem is a good fit for DP when it has both of these properties:

Overlapping subproblems — the same subproblems get computed many times if you solve it with plain recursion.

Optimal substructure — the optimal answer to the big problem is built from optimal answers to its subproblems.

Missing either property means DP may not fully help: overlapping subproblems alone is not enough (you still need to prove the subproblem answers actually combine into the optimal answer for the big one), and optimal substructure alone is not worth caching either (e.g. divide-and-conquer like merge sort, where the subproblems never repeat).

Top-down (Memoization) vs Bottom-up (Tabulation)

There are two main ways to write DP:

• Memoization (top-down) — write the most natural recursion, then store results in a cache. When you hit the same subproblem again, pull it from the cache instead of recomputing.
• Tabulation (bottom-up) — build a table and fill it from the smallest subproblems upward to the big one, with no recursion at all.

	Top-down (Memoization)	Bottom-up (Tabulation)
How it’s written	natural recursion + cache	a loop (for/while) filling a table in order
Which subproblems get computed	only the ones actually called	every subproblem, in a fixed order
Stack overflow risk	risky if n is large (hits Python’s recursion limit)	no risk — no recursion
Easiest to derive from	the recurrence, directly	you must work out the fill order yourself
Optimizing memory later	hard (the cache structure is tied to the recursion)	easy (can often collapse to a 1D rolling array)

Key takeaway: DP isn’t one algorithm — it’s “remembering.” Whenever you see a recursion that recomputes the same value repeatedly, suspect it can take memoization or tabulation.

Worked example: Fibonacci

The Fibonacci sequence is F(0)=0, F(1)=1, and F(n) = F(n-1) + F(n-2).

A direct recursion is elegant but very slow:

def fib(n):
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)

This is O(2ⁿ) because the call tree branches into two at every level and recomputes the same values enormously often. For example, fib(5) calls fib(3) twice, fib(2) three times, and so on.

Drag the slider in the widget above and watch how fast the call tree branches out — notice how often the same-colored nodes (repeated subproblems) reappear as n grows. The real numbers are even scarier:

n	approx. number of function calls	approx. time
10	~177	instant
20	~21,891	a fraction of a second
30	~2,692,537	~1 second
40	~331,160,281	several minutes
50	~4 × 10¹⁰	several hours to days

*Actual time depends on the machine — the point is the exponential growth pattern: every +10 to n multiplies the time by thousands.

Fix it with memoization by storing computed results:

def fib(n, memo={}):
    if n < 2:
        return n
    if n in memo:
        return memo[n]
    memo[n] = fib(n - 1, memo) + fib(n - 2, memo)
    return memo[n]

Or use functools.lru_cache to make it shorter:

from functools import lru_cache

@lru_cache(maxsize=None)
def fib(n):
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)

Both versions reduce the complexity to O(n), because each value fib(k) is computed for real only once and is pulled straight from the cache afterward. The bushy call tree collapses into a straight line — that is the heart of DP.

Careful: def fib(n, memo={}) uses a mutable default argument. In Python, the default value is created once, when the function is defined — not on every call. This is normally a dangerous anti-pattern, but here it’s used intentionally to let the cache persist across calls. If that’s not your intent, use lru_cache instead — it’s safer (see Exercise 2).

Worked example: Unique Paths (a 2D DP table)

Problem: A robot sits at the top-left of an m × n grid and can only move right or down, one cell at a time. How many distinct paths reach the bottom-right corner?

Recurrence: the only way to reach cell (i, j) is from the cell above (i-1, j) or the cell to the left (i, j-1).

dp[i][j] = dp[i-1][j] + dp[i][j-1]
dp[0][j] = 1   (top row — only one way in, straight across)
dp[i][0] = 1   (left column — only one way in, straight down)

This is a very clean example of bottom-up tabulation: we fill the table starting from the small cases (the first row/column) up to the target cell, with no recursion at all.

Watch the widget above fill the table cell by cell. For a 4-row × 5-column grid, the final values are:

	col 0	col 1	col 2	col 3	col 4
row 0	1	1	1	1	1
row 1	1	2	3	4	5
row 2	1	3	6	10	15
row 3	1	4	10	20	35

The answer is the bottom-right cell: 35 paths.

def unique_paths(m: int, n: int) -> int:
    dp = [[1] * n for _ in range(m)]
    for i in range(1, m):
        for j in range(1, n):
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
    return dp[m - 1][n - 1]

Complexity: O(m·n) in both time and space, since we fill every cell in the table exactly once. (See the later exercises for how to shrink the space to O(n).)

Worked example: Coin Change (minimum coins)

Problem: given coin denominations coins = [1, 2, 5], make change for amount = 11 using the fewest coins possible. How many coins does it take?

Recurrence: to make change for a, try every coin c with c ≤ a and see how many coins it takes to make a - c (the remainder), plus one more for the coin just used — pick the smallest.

dp[0] = 0
dp[a] = min(dp[a - c] + 1)  over every coin c with c ≤ a

The table filled from amount = 0 up to 11 (coins = [1, 2, 5]):

amount	0	1	2	3	4	5	6	7	8	9	10	11
dp[amount]	0	1	1	2	2	1	2	2	3	3	2	3

For instance dp[11] = 3 because 11 = 5 + 5 + 1 (3 coins), which beats always greedily grabbing the largest coin first (see the AI Code Critique section below for why “greedy” fails on some coin sets).

def coin_change(coins: list[int], amount: int) -> int:
    dp = [0] + [float("inf")] * amount
    for a in range(1, amount + 1):
        for c in coins:
            if c <= a:
                dp[a] = min(dp[a], dp[a - c] + 1)
    return dp[amount] if dp[amount] != float("inf") else -1

Complexity: O(amount × len(coins)) time, O(amount) space. A spot where AI commonly slips up: forgetting the -1 for unreachable amounts (e.g. coins = [5], amount = 3) — without checking for float("inf") at the end, it would return a nonsensical inf instead.

Graphs

If DP is about “remembering subproblem answers,” graphs are about “modeling” relationships between things in a shape a computer can reason about — friends on social media, roads between cities, links between web pages, tasks that must run before other tasks (dependencies) — all of these are just “connected nodes.”

A graph is a data structure made of nodes (vertices) and edges that describe relationships between nodes.

• Directed — an edge goes one way, e.g. A → B (like a “follow” on social media).
• Undirected — an edge goes both ways, e.g. A — B (like a mutual friendship).

Adjacency List vs Adjacency Matrix

There are two main ways to store a graph in memory, and picking the wrong one is one of the most common sources of programs that are too slow or too memory-hungry:

	Adjacency List	Adjacency Matrix
Structure	each node keeps a list of its neighbors	a 2D V × V table
Memory	O(V + E) — efficient for sparse graphs	always O(V²), regardless of how many edges exist
Check if A-B are connected	O(deg(A)) — must scan the list	O(1) — look up cell [A][B] directly
Iterate all neighbors of a node	O(deg(v)) — fast, since only real neighbors are stored	O(V) — must scan the whole row even if there are few neighbors
Best for	sparse graphs (roads, social networks, dependency graphs) — most real-world graphs	dense graphs, or small graphs needing very frequent connectivity checks

Rule of thumb: real-world graphs tend to be sparse (E is closer to V than to V²) — when in doubt, start with an adjacency list.

BFS vs DFS

Both are ways to traverse a graph, but they explore in a completely different order:

• BFS (Breadth-First Search) — explores “broadly,” level by level from the start; it visits all neighbors first before going deeper. Uses a queue.
• DFS (Depth-First Search) — explores “deeply,” following one branch to the end before backtracking. Uses a stack (or recursion, which is really a stack the runtime manages for you).

Run both BFS and DFS on the same graph in the widget above, and notice how different the visitation order is.

	BFS	DFS
Data structure	Queue (FIFO)	Stack (LIFO) or recursion
Exploration order	level by level	as deep as possible, then backtrack
Shortest path (unweighted)	guaranteed — the first time you reach a node, it’s the closest	not guaranteed — may find a longer route first
Worst-case memory	stores a whole level (can be very wide for bushy graphs)	stores only the deepest path (often cheaper on wide graphs)
Use it for	shortest paths, “degrees of separation” (e.g. “friends of friends”), level-by-level web crawling	cycle detection, topological sort, counting connected components, backtracking problems (mazes, sudoku)

Key point: BFS gives the shortest path in an unweighted graph, because it spreads out one level at a time, so the first time you reach a node it must be the closest. Both BFS and DFS have the same complexity, O(V + E) — they differ in order, not speed.

A BFS example with a queue:

from collections import deque

def bfs(graph, start):
    visited = {start}
    queue = deque([start])
    order = []
    while queue:
        node = queue.popleft()
        order.append(node)
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)
    return order

A recursive DFS (short, readable, but risks stack overflow on very deep graphs):

def dfs_recursive(graph, node, visited=None, order=None):
    if visited is None:
        visited, order = set(), []
    visited.add(node)
    order.append(node)
    for neighbor in graph[node]:
        if neighbor not in visited:
            dfs_recursive(graph, neighbor, visited, order)
    return order

An iterative DFS with an explicit stack (no recursion-limit risk):

def dfs_iterative(graph, start):
    visited = {start}
    stack = [start]
    order = []
    while stack:
        node = stack.pop()
        order.append(node)
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                stack.append(neighbor)
    return order

Key takeaway: BFS and DFS use the exact same skeleton — the only difference is queue.popleft() (BFS) versus stack.pop() (DFS) — yet the results are entirely different. Remembering that one-line difference is the easiest way to keep them straight.

Warning: AI frequently produces DP and graph code that “looks right but is subtly wrong” — e.g. a wrong recurrence, a missing base case, or a missing visited set that causes an infinite loop when the graph has a cycle. All of this compiles and runs fine on tiny examples but fails silently on real data. Do not trust AI-generated code immediately — always test and verify it.

Real-world problem

Problem: shortest path in a grid using BFS

Given a grid where 0 is walkable and 1 is a wall, start at the top-left (0,0) and reach the bottom-right corner. Find the minimum number of steps — this is the core of game pathfinding, warehouse-robot navigation, and even routing a robot vacuum.

We model each cell as a node and adjacent cells (up/down/left/right) as edges, then use BFS because every step has equal “weight” — so BFS gives the shortest path. DFS would find a path too, but it wouldn’t be guaranteed to be the shortest one.

from collections import deque

def shortest_path(grid):
    rows, cols = len(grid), len(grid[0])
    start, goal = (0, 0), (rows - 1, cols - 1)
    if grid[0][0] == 1 or grid[goal[0]][goal[1]] == 1:
        return -1
    queue = deque([(start, 1)])          # (position, step count)
    visited = {start}
    while queue:
        (r, c), dist = queue.popleft()
        if (r, c) == goal:
            return dist
        for dr, dc in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
            nr, nc = r + dr, c + dc
            if 0 <= nr < rows and 0 <= nc < cols \
               and grid[nr][nc] == 0 and (nr, nc) not in visited:
                visited.add((nr, nc))
                queue.append(((nr, nc), dist + 1))
    return -1                            # unreachable

visited prevents looping back to the same cell, keeping the complexity at O(V + E), where V is the number of cells. Forget visited here and the program bounces back and forth between neighboring cells forever — the same bug family shown in the AI Code Critique section below.

Exercises

1. Big-O warm-up — what’s the approximate time complexity of a plain recursive coin-change solution with no memoization, compared to the tabulated version shown above?

Answer

Plain recursion with no memo: each a can branch into up to len(coins) ways and go as deep as amount levels, giving O(len(coins)^amount) — exponential, just like naive fib. The tabulated version above is O(amount × len(coins)), because each dp[a] is computed for real only once. This is exactly why DP turns an exponential problem into a polynomial one.

2. Predict the output — what does this code print, and why?

def fib(n, memo={}):
    if n < 2:
        return n
    if n in memo:
        return memo[n]
    memo[n] = fib(n - 1, memo) + fib(n - 2, memo)
    return memo[n]

print(fib(5))
print(len(fib.__defaults__[0]))
print(fib(3))

Answer

It prints 5, then 4 (because memo holds {2:1, 3:2, 4:3, 5:5} left over from the first call — a mutable default argument is created once, at function-definition time, not on every call), then 2 (pulled straight from the leftover cache, not recomputed). This example uses the mutable-default side effect intentionally so the cache persists across calls, but in ordinary code, relying on a mutable default unintentionally is a classic bug, since state leaks across calls in ways you didn’t expect. The safer approach is @lru_cache, or passing memo=None and creating a fresh one inside if it’s None.

3. Memoize a slow function — grid_paths(m, n) counts the number of paths from the top-left to the bottom-right corner (moving only right/down). Write it with recursion first, then add memoization.

Answer

from functools import lru_cache

@lru_cache(maxsize=None)
def grid_paths(m, n):
    if m == 1 or n == 1:
        return 1
    return grid_paths(m - 1, n) + grid_paths(m, n - 1)

Without memo: O(2^(m+n)) because of repeated branching. With memo: O(m·n), since each pair (m, n) is computed only once.

4. Climbing stairs — with n stairs and steps of 1 or 2 at a time, how many distinct ways are there to reach the top?

Answer

This is Fibonacci in disguise: ways to reach step n = ways to reach step n-1 (take a 1-step) + ways to reach step n-2 (take a 2-step).

def climb(n):
    a, b = 1, 1          # ways to reach step 0 and step 1
    for _ in range(n):
        a, b = b, a + b
    return a

5. Spot the bug — where does this coin-change code break? (Try it with coins=[2], amount=3.)

def coin_change(coins, amount):
    dp = [0] * (amount + 1)
    for a in range(1, amount + 1):
        for c in coins:
            if c <= a:
                dp[a] = min(dp[a], dp[a - c] + 1)
    return dp[amount]

Answer

Bug: dp is initialized with 0 instead of float("inf"). When an amount is unreachable (e.g. coins=[2], amount=3 — an odd number can never be made from 2s), the dp[a] entry that was never updated stays 0, and min(dp[a], dp[a-c]+1) will always pick 0 since it’s smaller than anything. The function ends up returning 0 (as if 0 coins made change!) instead of signaling failure.

Fix: initialize with dp = [0] + [float("inf")] * amount, then check at the end whether dp[amount] is still inf; if so, return -1.

6. Pick the right data structure — you have a social-media graph of ~10 million people, each with ~200 friends on average. You need to frequently check “are A and B friends?” Should you store this graph as an adjacency list or an adjacency matrix?

Answer

Adjacency list, because this graph is extremely sparse: V = 10,000,000 but E ≈ V × 200 / 2 = 1,000,000,000, which is vastly smaller than V² = 10^14. An adjacency matrix would need to store 10^14 cells — more memory than any machine on Earth has. Although an adjacency matrix gives O(1) connectivity checks, an adjacency list using a hash set for each person’s neighbor list gets nearly O(1) average-case lookups too, using only O(V + E) space.

7. Count graph components — given an undirected graph, count the number of connected components.

Answer

def count_components(graph, n):
    visited = set()
    count = 0
    for node in range(n):
        if node not in visited:
            count += 1
            stack = [node]                 # DFS
            while stack:
                cur = stack.pop()
                if cur in visited:
                    continue
                visited.add(cur)
                stack.extend(graph[cur])
    return count

Uses DFS (BFS would work identically here — the visitation order doesn’t matter for this problem). It scans every node that hasn’t been visited yet; each time it finds an unvisited node, that’s a new component, and it fully explores that component before counting the next one.

8. BFS shortest path — in an unweighted graph, find the minimum number of edges between node start and target.

Answer

from collections import deque

def shortest(graph, start, target):
    if start == target:
        return 0
    visited = {start}
    queue = deque([(start, 0)])
    while queue:
        node, dist = queue.popleft()
        for nxt in graph[node]:
            if nxt == target:
                return dist + 1
            if nxt not in visited:
                visited.add(nxt)
                queue.append((nxt, dist + 1))
    return -1

This must use BFS, not DFS, because DFS might reach target via a longer detour first and return the wrong distance.

9. Improve this code — the unique_paths shown earlier uses O(m·n) memory because it stores the entire 2D table, even though filling each row only ever needs “the previous row.” Rewrite it to use O(n) memory with a rolling array (a single row).

Answer

def unique_paths(m: int, n: int) -> int:
    row = [1] * n
    for _ in range(1, m):
        for j in range(1, n):
            row[j] += row[j - 1]   # row[j]'s old value = the value from the row above
    return row[-1]

Since dp[i][j] = dp[i-1][j] + dp[i][j-1] only ever needs “the cell above, same column” and “the cell to the left, same row,” a single array can be recycled. Right before row[j] is updated, it still holds dp[i-1][j] (the row above); adding row[j-1] (already updated to the current row) gives exactly dp[i][j]. This trick shrinks memory for a huge range of 2D DP problems.

AI Code Critique

Case 1: DP — when “greedy” looks right but isn’t

Someone asked an AI to write a function that makes change with the fewest coins, and got this back:

def coin_change(coins, amount):
    coins.sort(reverse=True)
    count = 0
    for c in coins:
        while amount >= c:
            amount -= c
            count += 1
    return count if amount == 0 else -1

This is greedy: always grab the largest coin first. It runs perfectly on coins=[1,5,10,25] (US coins), getting the right answer every time, because that particular coin set happens to have a special property (a canonical coin system). But try it with coins=[1,3,4], amount=6.

Answer

Bug: greedy is not DP and does not guarantee the optimal answer in general. With coins=[1,3,4], amount=6: greedy grabs 4 first (2 left), then 1 twice (0 left), for a total of 3 coins (4+1+1). But the true optimum is 3+3 = 2 coins — fewer!

This is a classic mistake AI produces very often, because greedy “looks right” on US/Thai coin denominations (which happen to form a canonical coin system) but silently fails on other coin sets. This problem requires DP, because there is no general proof that greedy works for every possible set of coins.

Fix: use DP tabulation as in the Worked Example above (dp[a] = min(dp[a-c]+1)), which always guarantees the optimal answer, no matter what the coin set is.

Lesson: whenever an AI proposes greedy for a “find the minimum/maximum” problem, ask it back “can you prove this greedy choice never loses to any other choice?” If it can’t, suspect the problem actually needs DP.

Case 2: Graph — when AI forgets visited

Someone asked an AI to write a graph traversal function and got this back:

def traverse(graph, start):
    order = []
    queue = [start]
    while queue:
        node = queue.pop(0)
        order.append(node)
        for neighbor in graph[node]:
            queue.append(neighbor)      # <-- ?
    return order

This runs fine on a tree (a graph with no cycles), but… find the bug. What happens on a cyclic graph such as A — B and B — A?

Answer

Bug: there is no visited set. When the graph has a cycle, nodes get added to the queue over and over forever → infinite loop, and order grows without bound until memory runs out.

This is a classic mistake AI produces very often, because it tested only on a small acyclic graph where it “looks right.”

Fix: add a visited set so no node is visited twice.

from collections import deque

def traverse(graph, start):
    order = []
    visited = {start}
    queue = deque([start])
    while queue:
        node = queue.popleft()
        order.append(node)
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)
    return order

Lesson: when an AI hands you graph code, check for visited first, and always test on a graph with a cycle.

🎮 Game Dev: A* Pathfinding and DP for Gold Collection

The BFS we just saw above is the heart of enemy pathfinding in real games. But most games want an enemy to move toward the player “smartly,” not just spread out equally in every direction — that’s where A* takes over from BFS by adding a heuristic that helps prioritize which tile to explore next. On the flip side, the Unique Paths DP table we just worked through converts into a game problem immediately: instead of “counting paths,” try finding the path that collects the most gold.

A* Pathfinding on a Tile Grid

Treat each tile as a node and adjacent tiles (up/down/left/right) as edges — exactly like the “shortest path in a grid” problem above. But BFS has a downside on large graphs: it spreads out equally in every direction, even the ones pointing away from the goal get explored just as thoroughly — wasting time once the map has thousands of tiles.

A* fixes this by swapping the plain queue for a priority queue ordered by f = g + h, where g is the actual distance traveled so far and h is a heuristic estimating the remaining distance (here, Manhattan distance: |dx| + |dy|, since movement is only 4-directional with no diagonals). The result is that A* always explores the tile that “looks like it’s heading toward the goal” first, instead of exploring every direction equally the way BFS does.

import heapq

def manhattan(a: tuple[int, int], b: tuple[int, int]) -> int:
    return abs(a[0] - b[0]) + abs(a[1] - b[1])

def astar(grid: list[list[int]], start: tuple[int, int],
          goal: tuple[int, int]) -> list[tuple[int, int]]:
    rows, cols = len(grid), len(grid[0])
    frontier = [(manhattan(start, goal), 0, start)]   # (f, g, tile)
    came_from = {start: None}
    cost_so_far = {start: 0}
    while frontier:
        _, g, current = heapq.heappop(frontier)
        if current == goal:
            break
        for dr, dc in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
            nr, nc = current[0] + dr, current[1] + dc
            neighbor = (nr, nc)
            if not (0 <= nr < rows and 0 <= nc < cols) or grid[nr][nc] == 1:
                continue                       # off the grid, or a wall
            new_cost = g + 1
            if neighbor not in cost_so_far or new_cost < cost_so_far[neighbor]:
                cost_so_far[neighbor] = new_cost
                priority = new_cost + manhattan(neighbor, goal)
                heapq.heappush(frontier, (priority, new_cost, neighbor))
                came_from[neighbor] = current
    path, node = [], goal
    while node is not None:
        path.append(node)
        node = came_from.get(node)
    return path[::-1]

Both BFS and A* guarantee the shortest path on an unweighted graph — the difference is that A explores far fewer tiles* when the heuristic points the right way. The bigger the map, the more dramatic the effect (see Exercise 1).

Figure: dark tiles are walls; the orange path is the route A chose from S to G.*

Try clicking tiles in the widget above to place your own walls, then hit find path and watch how A* dodges the walls while beelining toward the goal.

DP for Maximum Gold Collection

Use the same grid graph as Unique Paths, but change the problem: each cell holds grid[i][j] coins of gold. The robot can only move right/down, and you want to know the most gold it can collect by the time it reaches the bottom-right corner.

The “dumbest” approach is recursion that tries every path and compares totals — fine on a small grid, but it explodes exponentially, because repeated paths get recomputed just like the plain recursive unique_paths shown above. Fix it with the same DP, just swap “add 1” (count paths) for “pick the best option” (max):

dp[i][j] = grid[i][j] + max(dp[i-1][j], dp[i][j-1])
dp[0][0] = grid[0][0]
dp[0][j] = dp[0][j-1] + grid[0][j]   (top row — only one way in)
dp[i][0] = dp[i-1][0] + grid[i][0]   (left column — only one way in)

def max_gold(grid: list[list[int]]) -> int:
    rows, cols = len(grid), len(grid[0])
    dp = [[0] * cols for _ in range(rows)]
    dp[0][0] = grid[0][0]
    for j in range(1, cols):
        dp[0][j] = dp[0][j - 1] + grid[0][j]
    for i in range(1, rows):
        dp[i][0] = dp[i - 1][0] + grid[i][0]
    for i in range(1, rows):
        for j in range(1, cols):
            dp[i][j] = grid[i][j] + max(dp[i - 1][j], dp[i][j - 1])
    return dp[rows - 1][cols - 1]

The skeleton is exactly the same as unique_paths — only + becomes max, plus adding the current cell’s gold value. Complexity stays O(m·n).

Use the widget above (a 4×5 table, same as the Unique Paths problem) and imagine each cell holds a gold value instead of “1” — each cell is still filled from the cell above and the cell to the left exactly as before; only the rule for combining values changes from addition to picking the best option.

Game Exercises

1. BFS vs A on a grid* — both BFS and A* find the shortest path on an unweighted grid identically. So where does A* actually win? Explain why, on a 100×100 tile map with no obstacles at all, A* should explore far fewer tiles than BFS.

Answer

BFS spreads out equally in every direction until it hits the goal, meaning it always explores tiles within a circular radius (a diamond shape on a grid graph) around the start first — even the directions pointing away from the goal get explored just as thoroughly. A*, using f = g + h, orders its priority queue so tiles the heuristic says are “close to the goal” always get popped and explored first, making the search lean toward the goal in a narrow cone instead of a full circle. The farther apart S and G actually are, the more tiles A* saves relative to BFS, proportionally.

2. The heuristic must be admissible — if you change the heuristic in the A* code above from manhattan(a, b) to manhattan(a, b) * 2, what happens to the resulting path?

Answer

A correct (admissible) heuristic must never overestimate the true remaining distance — Manhattan distance on a 4-directional grid is exactly admissible, since it’s the minimum possible true distance (there’s no shorter way). But manhattan(a, b) * 2 overestimates, causing A* to rush toward tiles that “look close to the goal” without waiting to compare against other routes whose g is actually cheaper. The result is that A* may return a path that is not the shortest (losing the optimality guarantee), even though it will still find some path to the goal — this is why heuristics must be chosen carefully; more isn’t better.

3. Write the recurrence for min-cost — instead of collecting the most gold, suppose the problem changes to “each cell costs cost[i][j] energy to cross, find the path that costs the least energy.” How does the recurrence change?

Answer

Just swap max for min — everything else stays the same:

def min_cost(cost: list[list[int]]) -> int:
    rows, cols = len(cost), len(cost[0])
    dp = [[0] * cols for _ in range(rows)]
    dp[0][0] = cost[0][0]
    for j in range(1, cols):
        dp[0][j] = dp[0][j - 1] + cost[0][j]
    for i in range(1, rows):
        dp[i][0] = dp[i - 1][0] + cost[i][0]
    for i in range(1, rows):
        for j in range(1, cols):
            dp[i][j] = cost[i][j] + min(dp[i - 1][j], dp[i][j - 1])
    return dp[rows - 1][cols - 1]

This is what makes grid-DP so useful: just swap the combining operation (+ → count paths, max → collect the most, min → spend the least), and the table-filling loop skeleton stays identical every time.

4. Spot the bug — what did this max_gold code forget? (The bug surfaces when grid contains negative values, e.g. a trap cell that costs points.)

def max_gold(grid):
    rows, cols = len(grid), len(grid[0])
    dp = [[0] * cols for _ in range(rows)]
    for i in range(rows):
        for j in range(cols):
            best = max(dp[i - 1][j] if i > 0 else 0,
                       dp[i][j - 1] if j > 0 else 0)
            dp[i][j] = grid[i][j] + best
    return dp[rows - 1][cols - 1]

Answer

This code is actually correct for the general case (i > 0 else 0 and j > 0 else 0 already handle the base cases) — even a negative grid[0][0] still computes correctly. But the hidden gap is: this recurrence has no notion of walls or impassable cells, unlike A* (which handles it via grid[nr][nc] == 1). If the problem adds “some cells simply cannot be entered,” this code will still compute dp[i][j] from a wall cell as if it were freely walkable. You’d need to add a check that if the current cell is a wall, set dp[i][j] = -infinity (or skip it entirely) first — the lesson: grid-DP that works fine on an open grid can fail silently the moment the problem adds walls or obstacles, unless you add that guard yourself.

Challenge Problems

1. Weighted terrain (weighted A)* — in a real game, not every tile takes the same time to cross: normal grass costs 1, mud costs 3, shallow water costs 5. Adapt astar() above to work with a cost_grid instead of pure 0/1 walls (hint: new_cost = g + cost_grid[nr][nc] instead of g + 1 — but why does the Manhattan heuristic still need to “never overestimate”?)

Approach

Just change the new_cost line from g + 1 to g + cost_grid[nr][nc]; the priority queue and came_from structure stay exactly the same — this is A* in its full form (differing from Dijkstra only in that a heuristic helps order the queue). The important catch: if the terrain’s lowest possible cost is min_cost (e.g. 1 for grass), the heuristic must also be multiplied by that min_cost — e.g. manhattan(a, b) * min_cost, not plain manhattan(a, b) — otherwise the heuristic will overestimate whenever most terrain costs more than 1 (losing admissibility, same failure as Exercise 2). The safest general fallback, if you don’t know the minimum cost in advance, is to set the heuristic to 0 everywhere (this degenerates into plain Dijkstra) — always safe, but slower.

2. Pick items for maximum power under a weight budget (knapsack) — a character has a bag that can carry at most capacity weight, with items to choose from [(weight, power), ...], each item pickable only once (0/1 knapsack). Find the set of items that maximizes total power without exceeding capacity. How is this different from grid-DP, and what should the DP state be?

Approach

Grid-DP’s state dimension is “position on the grid” (i, j), but knapsack’s state dimension is “how many items considered so far” × “remaining weight budget.” Define dp[k][w] = the maximum power achievable by choosing among the first k items with total weight at most w. The recurrence for item k (weight wt, power pw):

dp[k][w] = dp[k-1][w]                                    if wt > w (can't fit)
dp[k][w] = max(dp[k-1][w], dp[k-1][w-wt] + pw)           if wt <= w (take it or skip it)

Fill the table from k=0 to k=len(items), w=0 to capacity; the answer sits at dp[len(items)][capacity]. Complexity is O(len(items) × capacity) — like grid-DP, it fills a 2D table bottom-up row by row, but the second dimension isn’t a map position, it’s “remaining weight budget.” (This is the classic DP pattern called 0/1 Knapsack, applicable to a “loadout” problem in nearly any game with weight/slot/mana constraints.)

Going deeper

• MIT 6.006 — Introduction to Algorithms (OpenCourseWare) — free lectures on DP and graph search.
• Stanford CS161 — Design and Analysis of Algorithms — covers BFS/DFS and shortest paths.
• CLRS — Introduction to Algorithms, Chapters 14–15 (Dynamic Programming) and Chapters 20–22 (Elementary Graph Algorithms, BFS/DFS) — the standard reference, with rigorous correctness proofs for every algorithm.
• Kleinberg & Tardos — Algorithm Design — teaches how to design DP and graph solutions from scratch; excellent at the process of deriving a recurrence, not just reciting one.
• Sedgewick & Wayne — Algorithms (4th ed.) — clean, readable graph implementations covering adjacency lists/matrices and BFS/DFS in detail, with strong illustrations.
• Erickson — Algorithms (free online) — an outstanding chapter on Dynamic Programming that teaches “how to find the recurrence” as a repeatable process, not just showing finished answers.
• Roughgarden — Algorithms Illuminated — explains DP and graphs accessibly while staying rigorous; a great companion to Stanford CS161.
• Visualgo.net — interactive animations of BFS/DFS that make the traversal order easy to see.