What is the pricing and subscription model for Hi👋SpeedAlgo?

The entire core curriculum of 13 patterns and 225 practice problems is 100% free to access with no credit card required. New accounts get 40 free coins once, the daily claim adds +20 coins once a day, and inviting a friend earns you +25 coins when they complete their first practice step. These are the only ways to earn coins. Each AI coach question costs 1-5 coins, priced by the server according to its size. AI coaching is free with your own Google Gemini, OpenAI or OpenRouter API key (BYOK). Coins also unlock extras for 24 hours: a Recall hint level (1 coin), a Solve solution reveal (2), a LeetCode problem card's solutions (1) and a pattern's extra canonical problems (1). Nothing on the site is sold for money: coins can only be earned, never bought.

What is the refund and cancellation policy?

Hi👋SpeedAlgo sells nothing for money: there are no subscriptions, renewals or charges, so there is nothing to cancel or refund. Nothing on the site is sold for money: coins can only be earned, never bought.

Who creates and maintains the curriculum?

Hi👋SpeedAlgo is developed and maintained by Hi👋WebEnterprise (https://hiwebenterprise.com), an engineering organization focused on developer education, deliberate practice methodologies, and cognitive ergonomics for technical interviews.

How does Hi👋SpeedAlgo prepare candidates for senior and staff SWE interviews?

Rather than rote LeetCode grinding, Hi👋SpeedAlgo uses deliberate practice for each pattern: learn the loop invariant, Big-O proof and edge cases from a side-by-side template and a step-by-step debugger, rebuild the template from memory, then solve a new problem on your own against a graded test suite.

Theory Context•Dynamic Programming

Builds on Bottom-Up DFS, which you haven’t finished yet.

P0MediumMental model~3 min speedrun

Memoized Recursion (Top-Down DP, Memo DFS): a technique for any state shape

The problem

Decode Ways (LC 91)(opens leetcode.com)

A digit-only string was produced by encoding letters through the mapping "1" -> 'A', "2" -> 'B', ..., "25" -> 'Y', "26" -> 'Z'. Because some two-digit codes contain smaller valid one-digit codes inside them ("2" and "5" versus "25"), the same digit string can often be split into letters in more than one way.

For example, the digits "11106" can be grouped as (1, 1, 10, 6) to spell "AAJF", or as (11, 10, 6) to spell "KJF". Grouping it as (1, 11, 06) is not allowed, because "06" is not a valid code -- only "6" is.

Given a digit string s, count how many distinct ways it can be decoded this way, returning 0 when no valid decoding exists at all. Inputs are limited so the count always fits in a 32-bit integer.

Example 1

Input:s = "12"

Output:2

"12" could be decoded as "AB" (1 2) or "L" (12).

Memoization

brute-force recursion ➔ cache results by arguments ➔ each state solved once

Spot it when: The brute-force recursion is easy to write (count the ways, can you reach the end, the best score from here), but it calls itself again and again with the same arguments, and its answer depends on those arguments alone.

Memoization

Python

1	from typing import Callable, Dict, Hashable, TypeVar
2
3	R = TypeVar("R")
4
5
6	def memoize(recurrence: Callable[[Hashable, Callable[[Hashable], R]], R]) -> Callable[[Hashable], R]:
7	"""Memoization: solve(state) with each state's answer computed once and then looked up.
8	recurrence(state, solve) computes the answer for state, calling solve on smaller states.
9	Precondition: the answer depends only on state, and the calls never loop back to a state in progress.
10	S = distinct states. T = the cost of one recurrence call besides the solve calls it makes.
11	Time: O(S * T) \| Space: O(S) memo and recursion stack
12	"""
13	# memo: memo[state] holds the finished answer for state, once it has been computed
14	memo: Dict[Hashable, R] = {}
15
16	def solve(state: Hashable) -> R:
17	# 1. Compute Once, Then Reuse:
18	# The first call for a state runs the recurrence and stores the answer before returning, so
19	# every later call for the same state is a lookup instead of a repeated exploration.
20	if state not in memo:
21	memo[state] = recurrence(state, solve)
22	return memo[state]
23
24	return solve

Invariant: memo[index] is written only with the finished answer for s[index:], so every call after the first one for the same index returns it without exploring again.

The number of ways to decode s[index:] depends only on index, never on how the digits before it were split, so dfs(index) stores its answer in memo[index] the first time it finishes and returns that stored value on every later call. The plain recursion reaches the same index along many different split paths; with the memo, each index explores its one-digit and two-digit branches only once, and every repeated call is a lookup that returns exactly what exploring again would have returned. The trap is the key: memo must be keyed by every argument that changes the answer. Here that is index alone, but in Interleaving String (LC 97) the answer depends on how far both strings are used, so the key is (i, j); key by i alone and a call that has used 2 letters of s2 gets the answer stored for one that used 5.

See it run

Decode Ways with memo, step by step

calls 0served from memo 0

Each column is one index of s. The last column is the index len(s).

index the index of the current call
stored the memo entry that was just stored
reused a memo entry that answers the call without more work

Start: memo is empty. dfs(0) decodes s = "11111".

end

memo

1 / 17

Gotchas1 of 5

The trap
Gotcha 1: Keying memo by i when the answer depends on (i, j)
Mistake
```
memo[i] = res
```
Fix
```
memo[(i, j)] = res
```
What happens: memo must be keyed by every argument that changes the answer. In Decode Ways (LC 91), that is index alone. In Interleaving String (LC 97), dfs(i, j) depends on both i and j. With the key i, a call gets the answer stored for a different j.
Example: Interleaving String (LC 97): s1 = "a", s2 = "ab", s3 = "aba"
Mistake: returns FalseFix: returns True
Gotcha 2: Testing if memo.get(index) instead of if index in memo
Mistake
```
if memo.get(index):
```
Fix
```
if index in memo:
```
What happens: A stored 0 is a real answer. In "1130", every index before the unreadable "30" has 0 ways. memo.get(index) returns 0, which is falsy, so the test fails. The subtree is explored again on every call. The answer stays the same, but the run is as slow as without memo.
Gotcha 3: Returning res without storing it in memo
Mistake
```
return res
```
Fix
```
memo[index] = res
return res
```
What happens: Without memo[index] = res, the lookup never finds anything. Every later call explores the whole subtree again. The answer stays the same, but the run is as slow as the plain recursion.
Gotcha 4: Memoizing a dfs that also reads a shared visited set
Mistake
```
memo[u] = total
```
Fix
```
memo[(u, frozenset(visited))] = total
```
What happens: A stored answer is only correct when dfs depends on its arguments alone. A shared visited set also changes the answer of dfs(u). A later call from a different path gets an answer computed with other nodes blocked. Longest Increasing Path in a Matrix (LC 329) needs no visited set. A strictly increasing path never comes back to a cell, so dfs(r, c) is safe to store.
Example: Simple paths from node 0 to node 3 in graph = {0: [1, 2], 1: [2, 3], 2: [1, 3], 3: []}
Mistake: returns 3Fix: returns 4
Gotcha 5: Scanning for the next job linearly instead of with binary search
Mistake
```
for j in range(i + 1, n):
    if start[j] >= end[i]:
        nxt = j
        break
```
Fix
```
nxt = bisect_left(start, end[i])
```
What happens: Maximum Profit in Job Scheduling (LC 1235) sorts the jobs by start before the recursion runs, so start is sorted and the loop's own test, start[j] >= end[i], is true from some index onward and false before it. bisect_left(start, end[i]) finds that index directly. The linear scan finds the same index, because it checks the same condition one j at a time from i + 1. Both give the same profit. The linear scan costs up to O(n) per call to dfs(i), so O(n^2) time in all. The binary search costs O(log n) per call, so O(n log n) time in all.

Not this one if…

Every state is needed and you can name a fill order in advance (one line from the end, as in House Robber (LC 198)): a loop with two variables is simpler and needs no recursion stack. Use Memoization when only some states are reachable or the order is awkward, as in Longest Increasing Path in a Matrix (LC 329). See House Robber
The state is a pair of positions (i, j) in two strings or a grid, every pair is needed, and each cell reads only its neighbours up and to the left, as in Longest Common Subsequence (LC 1143): the order to fill a whole table is already known. See Two-Sequence DP

Deep Dive

Why storing an answer is correct

A stored answer is correct when the function is a pure function of its arguments. A pure function returns the same result every time it receives the same arguments, and it reads nothing else that can change.

In Decode Ways (LC 91), dfs(index) reads only s and index. s never changes. So dfs(index) returns the same number each time, and the second call can return memo[index] instead of exploring again.

This is why the card's invariant says memo[index] is written only with the finished answer. A value that is still being computed must never be stored, because a later call could read a partial result.

What counts as a state

A state is the smallest set of values that fully decides the answer of one call. In Decode Ways (LC 91), the state is index. The digits before index are already split, and the number of ways to decode s[index:] does not depend on how they were split.

To find the state, ask this question for each argument: if two calls differ only in this argument, can their answers differ? If yes, the argument belongs in the key. In Interleaving String (LC 97), dfs(i, j) needs both i and j, so the key is (i, j).

Keep the state small. Every extra value in the key multiplies the number of states.

The cost: number of states times work per state

The card's complexity line is O(S * T). S is the number of distinct states. T is the work one recurrence call does besides its solve calls.

For numDecodings, S = N indices and T = O(1), because each dfs(index) makes at most two calls and one comparison. The total is O(N) time and O(N) space for memo and the recursion stack.

Example: for s = "1" * 30, the plain recursion makes 3,524,577 calls. With memo, it makes 60 calls, which is two per index. Both return 1,346,269.

When you estimate the cost, count the reachable states, not the largest possible number of states. Memoization only visits the states that the recursion actually reaches.

Recursion depth is part of the cost

Each unfinished dfs call stays on the call stack until its sub-calls return. For numDecodings, the deepest chain is dfs(0), dfs(1), and so on up to dfs(len(s)). That is about len(s) calls.

Python allows about 1000 nested calls by default. With s = "1" * 2000, numDecodings raises RecursionError. LeetCode limits s to 100 characters, so the card's code is safe there.

If the depth can be large, write the same recurrence as a loop that fills dp from the end, or raise the limit with care.

60-Second Pitch

"The brute force tries one digit and then two digits at each position. It repeats the same suffix many times, so it takes exponential time. The number of ways to decode s[index:] depends only on index. So I add memo[index], and I store the answer just before dfs returns. There are N distinct indices, and each does constant work. That gives O(N) time, and O(N) space for memo and the recursion stack. I chose top-down because it follows the recurrence directly. If the depth were a problem, I would write the same recurrence as a loop from the end of the string."

Common Questions

What is the difference between top-down and bottom-up for this problem?: Both compute the same recurrence. Top-down (memoization) starts at dfs(0) and solves a state only when a call needs it. Bottom-up fills dp[i] for i from len(s) down to 0 in a fixed order. Bottom-up has no recursion stack, so it has no depth limit. Top-down is easier to write when the fill order is awkward or when only some states are reachable.
What is the time and space complexity of numDecodings with memo?: O(N) time and O(N) space. There are N distinct values of index, and each one does constant work. The space is memo plus the recursion stack, and both hold at most about N entries.
Why can a recursion stack be a problem, and what do you do about it?: Python raises RecursionError after about 1000 nested calls, and numDecodings nests about len(s) calls. LeetCode limits s to 100 characters, so it is safe there. For a long input, use a bottom-up loop. Raising the recursion limit is a last choice, because a very deep stack can still crash the process.
Can a list be part of the memo key?: No. A list can change, so Python does not allow it as a dictionary key and raises TypeError. Convert the list to a tuple, or a set to a frozenset. Then check that the number of distinct keys is still small, because a large key makes the state count very large.
How do you know that memoization is allowed for a recursion?: Check two things. First, the answer of a call depends only on its arguments, with no shared mutable value that changes the result. Second, the calls never return to a state that is still in progress. If a cycle exists, the stored value would be read before it is finished. Then the recursion needs a different method, such as a graph search.

SWE Reasoning

Spot it

You can write the brute-force recursion in one minute: count the ways, decide whether the end is reachable, or find the best score from here.
The recursion calls itself with the same arguments more than once, along different paths. Drawing the call tree for a short input shows repeated nodes.
The answer of a call depends on its arguments alone. It does not depend on the path that led to the call.
The number of distinct arguments is small, for example N indices or N * M pairs, while the number of paths is exponential.
Only some states are reachable, or the order in which to fill a table is hard to name. This favours top-down over a bottom-up loop.

The invariant, step by step

dfs(index) is called. The base cases run first: index == len(s) returns 1, and s[index] == "0" returns 0.
The function checks if index in memo. On the first call for this index, the key is missing, so the function continues.
It computes res = dfs(index + 1), and it adds dfs(index + 2) when the next two digits form a code from 10 to 26.
Only now does it write memo[index] = res. At this moment res is the finished answer for s[index:].
Every later call with the same index finds the key and returns the stored value. It explores nothing.
Because the answer depends on index alone, the stored value equals what exploring again would return. The result is correct, and each index is explored once.

Traps

Key is too small. If the answer depends on (i, j) and memo uses i, a call receives the answer stored for another j. The result is wrong. This happens in Interleaving String (LC 97).
Answer depends on hidden state. If dfs also reads a shared visited set, memo[u] mixes answers from different paths. The result is wrong. Put the changing value in the key, or redesign so that dfs needs no visited set.
Truthiness test. if memo.get(index): treats a stored 0 as missing, so zero-way indices are explored every time. The result stays right, but the run is slow. Use if index in memo.
Missing store. If memo[index] = res is absent, the lookup never succeeds. The result stays right, but the run is as slow as the plain recursion.
Mutable key. A list or a set cannot be a dictionary key, and Python raises TypeError: unhashable type: 'list'. Convert it to a tuple or a frozenset first.
Deep recursion. A chain of 2000 calls raises RecursionError in Python. Check the input limit before choosing top-down.

Practice

Canonical LeetCode:Decode Ways (LC 91)Longest Increasing Path in a Matrix (LC 329)Target Sum (LC 494)Word Break (LC 139)Concatenated Words (LC 472)Different Ways to Add Parentheses (LC 241)Maximum Profit in Job Scheduling (LC 1235)Interleaving String (LC 97)

Theory Context•Dynamic Programming

Builds on Bottom-Up DFS, which you haven’t finished yet.

P0MediumMental model~3 min speedrun

Memoized Recursion (Top-Down DP, Memo DFS): a technique for any state shape

The problem

Decode Ways (LC 91)(opens leetcode.com)

Given a digit string s, count how many distinct ways it can be decoded this way, returning 0 when no valid decoding exists at all. Inputs are limited so the count always fits in a 32-bit integer.

Example 1

Input:s = "12"

Output:2

"12" could be decoded as "AB" (1 2) or "L" (12).

Memoization

brute-force recursion ➔ cache results by arguments ➔ each state solved once

Memoization

Python

1	from typing import Callable, Dict, Hashable, TypeVar
2
3	R = TypeVar("R")
4
5
6	def memoize(recurrence: Callable[[Hashable, Callable[[Hashable], R]], R]) -> Callable[[Hashable], R]:
7	"""Memoization: solve(state) with each state's answer computed once and then looked up.
8	recurrence(state, solve) computes the answer for state, calling solve on smaller states.
9	Precondition: the answer depends only on state, and the calls never loop back to a state in progress.
10	S = distinct states. T = the cost of one recurrence call besides the solve calls it makes.
11	Time: O(S * T) \| Space: O(S) memo and recursion stack
12	"""
13	# memo: memo[state] holds the finished answer for state, once it has been computed
14	memo: Dict[Hashable, R] = {}
15
16	def solve(state: Hashable) -> R:
17	# 1. Compute Once, Then Reuse:
18	# The first call for a state runs the recurrence and stores the answer before returning, so
19	# every later call for the same state is a lookup instead of a repeated exploration.
20	if state not in memo:
21	memo[state] = recurrence(state, solve)
22	return memo[state]
23
24	return solve

Invariant: memo[index] is written only with the finished answer for s[index:], so every call after the first one for the same index returns it without exploring again.

See it run

Decode Ways with memo, step by step

calls 0served from memo 0

Each column is one index of s. The last column is the index len(s).

index the index of the current call
stored the memo entry that was just stored
reused a memo entry that answers the call without more work

Start: memo is empty. dfs(0) decodes s = "11111".

end

memo

1 / 17

Gotchas1 of 5

The trap
Gotcha 1: Keying memo by i when the answer depends on (i, j)
Mistake
```
memo[i] = res
```
Fix
```
memo[(i, j)] = res
```
What happens: memo must be keyed by every argument that changes the answer. In Decode Ways (LC 91), that is index alone. In Interleaving String (LC 97), dfs(i, j) depends on both i and j. With the key i, a call gets the answer stored for a different j.
Example: Interleaving String (LC 97): s1 = "a", s2 = "ab", s3 = "aba"
Mistake: returns FalseFix: returns True
Gotcha 2: Testing if memo.get(index) instead of if index in memo
Mistake
```
if memo.get(index):
```
Fix
```
if index in memo:
```
What happens: A stored 0 is a real answer. In "1130", every index before the unreadable "30" has 0 ways. memo.get(index) returns 0, which is falsy, so the test fails. The subtree is explored again on every call. The answer stays the same, but the run is as slow as without memo.
Gotcha 3: Returning res without storing it in memo
Mistake
```
return res
```
Fix
```
memo[index] = res
return res
```
What happens: Without memo[index] = res, the lookup never finds anything. Every later call explores the whole subtree again. The answer stays the same, but the run is as slow as the plain recursion.
Gotcha 4: Memoizing a dfs that also reads a shared visited set
Mistake
```
memo[u] = total
```
Fix
```
memo[(u, frozenset(visited))] = total
```
What happens: A stored answer is only correct when dfs depends on its arguments alone. A shared visited set also changes the answer of dfs(u). A later call from a different path gets an answer computed with other nodes blocked. Longest Increasing Path in a Matrix (LC 329) needs no visited set. A strictly increasing path never comes back to a cell, so dfs(r, c) is safe to store.
Example: Simple paths from node 0 to node 3 in graph = {0: [1, 2], 1: [2, 3], 2: [1, 3], 3: []}
Mistake: returns 3Fix: returns 4
Gotcha 5: Scanning for the next job linearly instead of with binary search
Mistake
```
for j in range(i + 1, n):
    if start[j] >= end[i]:
        nxt = j
        break
```
Fix
```
nxt = bisect_left(start, end[i])
```
What happens: Maximum Profit in Job Scheduling (LC 1235) sorts the jobs by start before the recursion runs, so start is sorted and the loop's own test, start[j] >= end[i], is true from some index onward and false before it. bisect_left(start, end[i]) finds that index directly. The linear scan finds the same index, because it checks the same condition one j at a time from i + 1. Both give the same profit. The linear scan costs up to O(n) per call to dfs(i), so O(n^2) time in all. The binary search costs O(log n) per call, so O(n log n) time in all.

Not this one if…

Every state is needed and you can name a fill order in advance (one line from the end, as in House Robber (LC 198)): a loop with two variables is simpler and needs no recursion stack. Use Memoization when only some states are reachable or the order is awkward, as in Longest Increasing Path in a Matrix (LC 329). See House Robber
The state is a pair of positions (i, j) in two strings or a grid, every pair is needed, and each cell reads only its neighbours up and to the left, as in Longest Common Subsequence (LC 1143): the order to fill a whole table is already known. See Two-Sequence DP

Deep Dive

Why storing an answer is correct

What counts as a state

Keep the state small. Every extra value in the key multiplies the number of states.

The cost: number of states times work per state

The card's complexity line is O(S * T). S is the number of distinct states. T is the work one recurrence call does besides its solve calls.

For numDecodings, S = N indices and T = O(1), because each dfs(index) makes at most two calls and one comparison. The total is O(N) time and O(N) space for memo and the recursion stack.

Example: for s = "1" * 30, the plain recursion makes 3,524,577 calls. With memo, it makes 60 calls, which is two per index. Both return 1,346,269.

When you estimate the cost, count the reachable states, not the largest possible number of states. Memoization only visits the states that the recursion actually reaches.

Recursion depth is part of the cost

Python allows about 1000 nested calls by default. With s = "1" * 2000, numDecodings raises RecursionError. LeetCode limits s to 100 characters, so the card's code is safe there.

If the depth can be large, write the same recurrence as a loop that fills dp from the end, or raise the limit with care.

60-Second Pitch

Common Questions

What is the difference between top-down and bottom-up for this problem?: Both compute the same recurrence. Top-down (memoization) starts at dfs(0) and solves a state only when a call needs it. Bottom-up fills dp[i] for i from len(s) down to 0 in a fixed order. Bottom-up has no recursion stack, so it has no depth limit. Top-down is easier to write when the fill order is awkward or when only some states are reachable.
What is the time and space complexity of numDecodings with memo?: O(N) time and O(N) space. There are N distinct values of index, and each one does constant work. The space is memo plus the recursion stack, and both hold at most about N entries.
Why can a recursion stack be a problem, and what do you do about it?: Python raises RecursionError after about 1000 nested calls, and numDecodings nests about len(s) calls. LeetCode limits s to 100 characters, so it is safe there. For a long input, use a bottom-up loop. Raising the recursion limit is a last choice, because a very deep stack can still crash the process.
Can a list be part of the memo key?: No. A list can change, so Python does not allow it as a dictionary key and raises TypeError. Convert the list to a tuple, or a set to a frozenset. Then check that the number of distinct keys is still small, because a large key makes the state count very large.
How do you know that memoization is allowed for a recursion?: Check two things. First, the answer of a call depends only on its arguments, with no shared mutable value that changes the result. Second, the calls never return to a state that is still in progress. If a cycle exists, the stored value would be read before it is finished. Then the recursion needs a different method, such as a graph search.

SWE Reasoning

Spot it

You can write the brute-force recursion in one minute: count the ways, decide whether the end is reachable, or find the best score from here.
The recursion calls itself with the same arguments more than once, along different paths. Drawing the call tree for a short input shows repeated nodes.
The answer of a call depends on its arguments alone. It does not depend on the path that led to the call.
The number of distinct arguments is small, for example N indices or N * M pairs, while the number of paths is exponential.
Only some states are reachable, or the order in which to fill a table is hard to name. This favours top-down over a bottom-up loop.

The invariant, step by step

dfs(index) is called. The base cases run first: index == len(s) returns 1, and s[index] == "0" returns 0.
The function checks if index in memo. On the first call for this index, the key is missing, so the function continues.
It computes res = dfs(index + 1), and it adds dfs(index + 2) when the next two digits form a code from 10 to 26.
Only now does it write memo[index] = res. At this moment res is the finished answer for s[index:].
Every later call with the same index finds the key and returns the stored value. It explores nothing.
Because the answer depends on index alone, the stored value equals what exploring again would return. The result is correct, and each index is explored once.

Traps

Key is too small. If the answer depends on (i, j) and memo uses i, a call receives the answer stored for another j. The result is wrong. This happens in Interleaving String (LC 97).
Answer depends on hidden state. If dfs also reads a shared visited set, memo[u] mixes answers from different paths. The result is wrong. Put the changing value in the key, or redesign so that dfs needs no visited set.
Truthiness test. if memo.get(index): treats a stored 0 as missing, so zero-way indices are explored every time. The result stays right, but the run is slow. Use if index in memo.
Missing store. If memo[index] = res is absent, the lookup never succeeds. The result stays right, but the run is as slow as the plain recursion.
Mutable key. A list or a set cannot be a dictionary key, and Python raises TypeError: unhashable type: 'list'. Convert it to a tuple or a frozenset first.
Deep recursion. A chain of 2000 calls raises RecursionError in Python. Check the input limit before choosing top-down.

Practice

Theory Context•Dynamic Programming

Builds on Bottom-Up DFS, which you haven’t finished yet.

P0MediumMental model~3 min speedrun

Memoized Recursion (Top-Down DP, Memo DFS): a technique for any state shape

The problem

Decode Ways (LC 91)(opens leetcode.com)

Given a digit string s, count how many distinct ways it can be decoded this way, returning 0 when no valid decoding exists at all. Inputs are limited so the count always fits in a 32-bit integer.

Example 1

Input:s = "12"

Output:2

"12" could be decoded as "AB" (1 2) or "L" (12).

Memoization

brute-force recursion ➔ cache results by arguments ➔ each state solved once

Memoization

Python

1	from typing import Callable, Dict, Hashable, TypeVar
2
3	R = TypeVar("R")
4
5
6	def memoize(recurrence: Callable[[Hashable, Callable[[Hashable], R]], R]) -> Callable[[Hashable], R]:
7	"""Memoization: solve(state) with each state's answer computed once and then looked up.
8	recurrence(state, solve) computes the answer for state, calling solve on smaller states.
9	Precondition: the answer depends only on state, and the calls never loop back to a state in progress.
10	S = distinct states. T = the cost of one recurrence call besides the solve calls it makes.
11	Time: O(S * T) \| Space: O(S) memo and recursion stack
12	"""
13	# memo: memo[state] holds the finished answer for state, once it has been computed
14	memo: Dict[Hashable, R] = {}
15
16	def solve(state: Hashable) -> R:
17	# 1. Compute Once, Then Reuse:
18	# The first call for a state runs the recurrence and stores the answer before returning, so
19	# every later call for the same state is a lookup instead of a repeated exploration.
20	if state not in memo:
21	memo[state] = recurrence(state, solve)
22	return memo[state]
23
24	return solve

Invariant: memo[index] is written only with the finished answer for s[index:], so every call after the first one for the same index returns it without exploring again.

See it run

Decode Ways with memo, step by step

calls 0served from memo 0

Each column is one index of s. The last column is the index len(s).

index the index of the current call
stored the memo entry that was just stored
reused a memo entry that answers the call without more work

Start: memo is empty. dfs(0) decodes s = "11111".

end

memo

1 / 17

Gotchas1 of 5

The trap
Gotcha 1: Keying memo by i when the answer depends on (i, j)
Mistake
```
memo[i] = res
```
Fix
```
memo[(i, j)] = res
```
What happens: memo must be keyed by every argument that changes the answer. In Decode Ways (LC 91), that is index alone. In Interleaving String (LC 97), dfs(i, j) depends on both i and j. With the key i, a call gets the answer stored for a different j.
Example: Interleaving String (LC 97): s1 = "a", s2 = "ab", s3 = "aba"
Mistake: returns FalseFix: returns True
Gotcha 2: Testing if memo.get(index) instead of if index in memo
Mistake
```
if memo.get(index):
```
Fix
```
if index in memo:
```
What happens: A stored 0 is a real answer. In "1130", every index before the unreadable "30" has 0 ways. memo.get(index) returns 0, which is falsy, so the test fails. The subtree is explored again on every call. The answer stays the same, but the run is as slow as without memo.
Gotcha 3: Returning res without storing it in memo
Mistake
```
return res
```
Fix
```
memo[index] = res
return res
```
What happens: Without memo[index] = res, the lookup never finds anything. Every later call explores the whole subtree again. The answer stays the same, but the run is as slow as the plain recursion.
Gotcha 4: Memoizing a dfs that also reads a shared visited set
Mistake
```
memo[u] = total
```
Fix
```
memo[(u, frozenset(visited))] = total
```
What happens: A stored answer is only correct when dfs depends on its arguments alone. A shared visited set also changes the answer of dfs(u). A later call from a different path gets an answer computed with other nodes blocked. Longest Increasing Path in a Matrix (LC 329) needs no visited set. A strictly increasing path never comes back to a cell, so dfs(r, c) is safe to store.
Example: Simple paths from node 0 to node 3 in graph = {0: [1, 2], 1: [2, 3], 2: [1, 3], 3: []}
Mistake: returns 3Fix: returns 4
Gotcha 5: Scanning for the next job linearly instead of with binary search
Mistake
```
for j in range(i + 1, n):
    if start[j] >= end[i]:
        nxt = j
        break
```
Fix
```
nxt = bisect_left(start, end[i])
```
What happens: Maximum Profit in Job Scheduling (LC 1235) sorts the jobs by start before the recursion runs, so start is sorted and the loop's own test, start[j] >= end[i], is true from some index onward and false before it. bisect_left(start, end[i]) finds that index directly. The linear scan finds the same index, because it checks the same condition one j at a time from i + 1. Both give the same profit. The linear scan costs up to O(n) per call to dfs(i), so O(n^2) time in all. The binary search costs O(log n) per call, so O(n log n) time in all.

Not this one if…

Every state is needed and you can name a fill order in advance (one line from the end, as in House Robber (LC 198)): a loop with two variables is simpler and needs no recursion stack. Use Memoization when only some states are reachable or the order is awkward, as in Longest Increasing Path in a Matrix (LC 329). See House Robber
The state is a pair of positions (i, j) in two strings or a grid, every pair is needed, and each cell reads only its neighbours up and to the left, as in Longest Common Subsequence (LC 1143): the order to fill a whole table is already known. See Two-Sequence DP

Deep Dive

Why storing an answer is correct

What counts as a state

Keep the state small. Every extra value in the key multiplies the number of states.

The cost: number of states times work per state

The card's complexity line is O(S * T). S is the number of distinct states. T is the work one recurrence call does besides its solve calls.

For numDecodings, S = N indices and T = O(1), because each dfs(index) makes at most two calls and one comparison. The total is O(N) time and O(N) space for memo and the recursion stack.

Example: for s = "1" * 30, the plain recursion makes 3,524,577 calls. With memo, it makes 60 calls, which is two per index. Both return 1,346,269.

When you estimate the cost, count the reachable states, not the largest possible number of states. Memoization only visits the states that the recursion actually reaches.

Recursion depth is part of the cost

Python allows about 1000 nested calls by default. With s = "1" * 2000, numDecodings raises RecursionError. LeetCode limits s to 100 characters, so the card's code is safe there.

If the depth can be large, write the same recurrence as a loop that fills dp from the end, or raise the limit with care.

60-Second Pitch

Common Questions

What is the difference between top-down and bottom-up for this problem?: Both compute the same recurrence. Top-down (memoization) starts at dfs(0) and solves a state only when a call needs it. Bottom-up fills dp[i] for i from len(s) down to 0 in a fixed order. Bottom-up has no recursion stack, so it has no depth limit. Top-down is easier to write when the fill order is awkward or when only some states are reachable.
What is the time and space complexity of numDecodings with memo?: O(N) time and O(N) space. There are N distinct values of index, and each one does constant work. The space is memo plus the recursion stack, and both hold at most about N entries.
Why can a recursion stack be a problem, and what do you do about it?: Python raises RecursionError after about 1000 nested calls, and numDecodings nests about len(s) calls. LeetCode limits s to 100 characters, so it is safe there. For a long input, use a bottom-up loop. Raising the recursion limit is a last choice, because a very deep stack can still crash the process.
Can a list be part of the memo key?: No. A list can change, so Python does not allow it as a dictionary key and raises TypeError. Convert the list to a tuple, or a set to a frozenset. Then check that the number of distinct keys is still small, because a large key makes the state count very large.
How do you know that memoization is allowed for a recursion?: Check two things. First, the answer of a call depends only on its arguments, with no shared mutable value that changes the result. Second, the calls never return to a state that is still in progress. If a cycle exists, the stored value would be read before it is finished. Then the recursion needs a different method, such as a graph search.

SWE Reasoning

Spot it

You can write the brute-force recursion in one minute: count the ways, decide whether the end is reachable, or find the best score from here.
The recursion calls itself with the same arguments more than once, along different paths. Drawing the call tree for a short input shows repeated nodes.
The answer of a call depends on its arguments alone. It does not depend on the path that led to the call.
The number of distinct arguments is small, for example N indices or N * M pairs, while the number of paths is exponential.
Only some states are reachable, or the order in which to fill a table is hard to name. This favours top-down over a bottom-up loop.

The invariant, step by step

dfs(index) is called. The base cases run first: index == len(s) returns 1, and s[index] == "0" returns 0.
The function checks if index in memo. On the first call for this index, the key is missing, so the function continues.
It computes res = dfs(index + 1), and it adds dfs(index + 2) when the next two digits form a code from 10 to 26.
Only now does it write memo[index] = res. At this moment res is the finished answer for s[index:].
Every later call with the same index finds the key and returns the stored value. It explores nothing.
Because the answer depends on index alone, the stored value equals what exploring again would return. The result is correct, and each index is explored once.

Traps

Key is too small. If the answer depends on (i, j) and memo uses i, a call receives the answer stored for another j. The result is wrong. This happens in Interleaving String (LC 97).
Answer depends on hidden state. If dfs also reads a shared visited set, memo[u] mixes answers from different paths. The result is wrong. Put the changing value in the key, or redesign so that dfs needs no visited set.
Truthiness test. if memo.get(index): treats a stored 0 as missing, so zero-way indices are explored every time. The result stays right, but the run is slow. Use if index in memo.
Missing store. If memo[index] = res is absent, the lookup never succeeds. The result stays right, but the run is as slow as the plain recursion.
Mutable key. A list or a set cannot be a dictionary key, and Python raises TypeError: unhashable type: 'list'. Convert it to a tuple or a frozenset first.
Deep recursion. A chain of 2000 calls raises RecursionError in Python. Check the input limit before choosing top-down.

Practice

Theory Context•Dynamic Programming

Builds on Bottom-Up DFS, which you haven’t finished yet.

P0MediumMental model~3 min speedrun

Memoized Recursion (Top-Down DP, Memo DFS): a technique for any state shape

The problem

Decode Ways (LC 91)(opens leetcode.com)

Given a digit string s, count how many distinct ways it can be decoded this way, returning 0 when no valid decoding exists at all. Inputs are limited so the count always fits in a 32-bit integer.

Example 1

Input:s = "12"

Output:2

"12" could be decoded as "AB" (1 2) or "L" (12).

Memoization

brute-force recursion ➔ cache results by arguments ➔ each state solved once

Memoization

Python

1	from typing import Callable, Dict, Hashable, TypeVar
2
3	R = TypeVar("R")
4
5
6	def memoize(recurrence: Callable[[Hashable, Callable[[Hashable], R]], R]) -> Callable[[Hashable], R]:
7	"""Memoization: solve(state) with each state's answer computed once and then looked up.
8	recurrence(state, solve) computes the answer for state, calling solve on smaller states.
9	Precondition: the answer depends only on state, and the calls never loop back to a state in progress.
10	S = distinct states. T = the cost of one recurrence call besides the solve calls it makes.
11	Time: O(S * T) \| Space: O(S) memo and recursion stack
12	"""
13	# memo: memo[state] holds the finished answer for state, once it has been computed
14	memo: Dict[Hashable, R] = {}
15
16	def solve(state: Hashable) -> R:
17	# 1. Compute Once, Then Reuse:
18	# The first call for a state runs the recurrence and stores the answer before returning, so
19	# every later call for the same state is a lookup instead of a repeated exploration.
20	if state not in memo:
21	memo[state] = recurrence(state, solve)
22	return memo[state]
23
24	return solve

Invariant: memo[index] is written only with the finished answer for s[index:], so every call after the first one for the same index returns it without exploring again.

See it run

Decode Ways with memo, step by step

calls 0served from memo 0

Each column is one index of s. The last column is the index len(s).

index the index of the current call
stored the memo entry that was just stored
reused a memo entry that answers the call without more work

Start: memo is empty. dfs(0) decodes s = "11111".

end

memo

1 / 17

Gotchas1 of 5

The trap
Gotcha 1: Keying memo by i when the answer depends on (i, j)
Mistake
```
memo[i] = res
```
Fix
```
memo[(i, j)] = res
```
What happens: memo must be keyed by every argument that changes the answer. In Decode Ways (LC 91), that is index alone. In Interleaving String (LC 97), dfs(i, j) depends on both i and j. With the key i, a call gets the answer stored for a different j.
Example: Interleaving String (LC 97): s1 = "a", s2 = "ab", s3 = "aba"
Mistake: returns FalseFix: returns True
Gotcha 2: Testing if memo.get(index) instead of if index in memo
Mistake
```
if memo.get(index):
```
Fix
```
if index in memo:
```
What happens: A stored 0 is a real answer. In "1130", every index before the unreadable "30" has 0 ways. memo.get(index) returns 0, which is falsy, so the test fails. The subtree is explored again on every call. The answer stays the same, but the run is as slow as without memo.
Gotcha 3: Returning res without storing it in memo
Mistake
```
return res
```
Fix
```
memo[index] = res
return res
```
What happens: Without memo[index] = res, the lookup never finds anything. Every later call explores the whole subtree again. The answer stays the same, but the run is as slow as the plain recursion.
Gotcha 4: Memoizing a dfs that also reads a shared visited set
Mistake
```
memo[u] = total
```
Fix
```
memo[(u, frozenset(visited))] = total
```
What happens: A stored answer is only correct when dfs depends on its arguments alone. A shared visited set also changes the answer of dfs(u). A later call from a different path gets an answer computed with other nodes blocked. Longest Increasing Path in a Matrix (LC 329) needs no visited set. A strictly increasing path never comes back to a cell, so dfs(r, c) is safe to store.
Example: Simple paths from node 0 to node 3 in graph = {0: [1, 2], 1: [2, 3], 2: [1, 3], 3: []}
Mistake: returns 3Fix: returns 4
Gotcha 5: Scanning for the next job linearly instead of with binary search
Mistake
```
for j in range(i + 1, n):
    if start[j] >= end[i]:
        nxt = j
        break
```
Fix
```
nxt = bisect_left(start, end[i])
```
What happens: Maximum Profit in Job Scheduling (LC 1235) sorts the jobs by start before the recursion runs, so start is sorted and the loop's own test, start[j] >= end[i], is true from some index onward and false before it. bisect_left(start, end[i]) finds that index directly. The linear scan finds the same index, because it checks the same condition one j at a time from i + 1. Both give the same profit. The linear scan costs up to O(n) per call to dfs(i), so O(n^2) time in all. The binary search costs O(log n) per call, so O(n log n) time in all.

Not this one if…

Every state is needed and you can name a fill order in advance (one line from the end, as in House Robber (LC 198)): a loop with two variables is simpler and needs no recursion stack. Use Memoization when only some states are reachable or the order is awkward, as in Longest Increasing Path in a Matrix (LC 329). See House Robber
The state is a pair of positions (i, j) in two strings or a grid, every pair is needed, and each cell reads only its neighbours up and to the left, as in Longest Common Subsequence (LC 1143): the order to fill a whole table is already known. See Two-Sequence DP

Deep Dive

Why storing an answer is correct

What counts as a state

Keep the state small. Every extra value in the key multiplies the number of states.

The cost: number of states times work per state

The card's complexity line is O(S * T). S is the number of distinct states. T is the work one recurrence call does besides its solve calls.

For numDecodings, S = N indices and T = O(1), because each dfs(index) makes at most two calls and one comparison. The total is O(N) time and O(N) space for memo and the recursion stack.

Example: for s = "1" * 30, the plain recursion makes 3,524,577 calls. With memo, it makes 60 calls, which is two per index. Both return 1,346,269.

When you estimate the cost, count the reachable states, not the largest possible number of states. Memoization only visits the states that the recursion actually reaches.

Recursion depth is part of the cost

Python allows about 1000 nested calls by default. With s = "1" * 2000, numDecodings raises RecursionError. LeetCode limits s to 100 characters, so the card's code is safe there.

If the depth can be large, write the same recurrence as a loop that fills dp from the end, or raise the limit with care.

60-Second Pitch

Common Questions

What is the difference between top-down and bottom-up for this problem?: Both compute the same recurrence. Top-down (memoization) starts at dfs(0) and solves a state only when a call needs it. Bottom-up fills dp[i] for i from len(s) down to 0 in a fixed order. Bottom-up has no recursion stack, so it has no depth limit. Top-down is easier to write when the fill order is awkward or when only some states are reachable.
What is the time and space complexity of numDecodings with memo?: O(N) time and O(N) space. There are N distinct values of index, and each one does constant work. The space is memo plus the recursion stack, and both hold at most about N entries.
Why can a recursion stack be a problem, and what do you do about it?: Python raises RecursionError after about 1000 nested calls, and numDecodings nests about len(s) calls. LeetCode limits s to 100 characters, so it is safe there. For a long input, use a bottom-up loop. Raising the recursion limit is a last choice, because a very deep stack can still crash the process.
Can a list be part of the memo key?: No. A list can change, so Python does not allow it as a dictionary key and raises TypeError. Convert the list to a tuple, or a set to a frozenset. Then check that the number of distinct keys is still small, because a large key makes the state count very large.
How do you know that memoization is allowed for a recursion?: Check two things. First, the answer of a call depends only on its arguments, with no shared mutable value that changes the result. Second, the calls never return to a state that is still in progress. If a cycle exists, the stored value would be read before it is finished. Then the recursion needs a different method, such as a graph search.

SWE Reasoning

Spot it

You can write the brute-force recursion in one minute: count the ways, decide whether the end is reachable, or find the best score from here.
The recursion calls itself with the same arguments more than once, along different paths. Drawing the call tree for a short input shows repeated nodes.
The answer of a call depends on its arguments alone. It does not depend on the path that led to the call.
The number of distinct arguments is small, for example N indices or N * M pairs, while the number of paths is exponential.
Only some states are reachable, or the order in which to fill a table is hard to name. This favours top-down over a bottom-up loop.

The invariant, step by step

dfs(index) is called. The base cases run first: index == len(s) returns 1, and s[index] == "0" returns 0.
The function checks if index in memo. On the first call for this index, the key is missing, so the function continues.
It computes res = dfs(index + 1), and it adds dfs(index + 2) when the next two digits form a code from 10 to 26.
Only now does it write memo[index] = res. At this moment res is the finished answer for s[index:].
Every later call with the same index finds the key and returns the stored value. It explores nothing.
Because the answer depends on index alone, the stored value equals what exploring again would return. The result is correct, and each index is explored once.

Traps

Key is too small. If the answer depends on (i, j) and memo uses i, a call receives the answer stored for another j. The result is wrong. This happens in Interleaving String (LC 97).
Answer depends on hidden state. If dfs also reads a shared visited set, memo[u] mixes answers from different paths. The result is wrong. Put the changing value in the key, or redesign so that dfs needs no visited set.
Truthiness test. if memo.get(index): treats a stored 0 as missing, so zero-way indices are explored every time. The result stays right, but the run is slow. Use if index in memo.
Missing store. If memo[index] = res is absent, the lookup never succeeds. The result stays right, but the run is as slow as the plain recursion.
Mutable key. A list or a set cannot be a dictionary key, and Python raises TypeError: unhashable type: 'list'. Convert it to a tuple or a frozenset first.
Deep recursion. A chain of 2000 calls raises RecursionError in Python. Check the input limit before choosing top-down.