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

P0EasyMental model~3 min speedrun

1D DP (Linear DP)

Grows into

Best Sightseeing Pair Kadane's Algorithm House Robber

Unlocks

Unbounded Knapsack Grid DP 0/1 Knapsack LIS State Machine DP Tree State DP Josephus Problem Digit DP

The problem

Climbing Stairs (LC 70)(opens leetcode.com)

A staircase has n steps between you and the top, and on every move you advance exactly 1 or 2 steps.

Count how many distinct sequences of moves get you all the way from the bottom to step n.

Example 1

Input:n = 2

Output:2

Two move sequences reach the top: two single steps in a row, or one double step.

Linear DP

dp[i] = the answer for the first i steps ➔ built from dp[i-1] and dp[i-2] ➔ O(1) rolling registers

Spot it when: Items come in a line and the answer at position i is built only from the answers at the last one or two positions: steps of 1 or 2, counts of ways, best totals.

Linear DP

Python

1	from typing import Callable
2
3
4	def linear_dp(n: int, first_two: tuple[int, int], combine: Callable[[int, int, int], int]) -> int:
5	"""Linear DP: dp[i] is built from dp[i - 1] and dp[i - 2], kept in two rolling variables.
6	combine(prev1, prev2, i) returns dp[i] from the two answers before it.
7	Precondition: first_two is (dp[0], dp[1]) and n >= 1.
8	T = the time of one combine call.
9	Time: O(N * T) \| Space: O(1)
10	"""
11	# prev2, prev1: dp[i - 2] and dp[i - 1], the only two answers the next one needs
12	prev2, prev1 = first_two
13	for i in range(2, n + 1):
14	# 1. Build dp[i] From The Last Two Answers:
15	# Both answers are final, so one call to combine gives dp[i] without looking further back.
16	curr = combine(prev1, prev2, i)
17
18	# 2. Roll The Window Forward:
19	# prev2 takes the old prev1 first, because prev1 is overwritten on the next line.
20	prev2 = prev1
21	prev1 = curr
22
23	return prev1

Invariant: After each step i, prev1 is dp[i] and prev2 is dp[i - 1].

dp[i] depends only on dp[i - 1] and dp[i - 2], so keep just those two answers in prev1 and prev2 and move them forward once per step, instead of storing a table. Decide what dp[i] means before writing the formula. Each dp[i] is built from two answers that are already final, so every answer is computed once, in order, and dp[n] is complete when the loop ends. The trap is the shift: set prev2 = prev1 before prev1 = curr, or prev2 is overwritten by the new value and both variables hold the same answer.

See it run

Climbing Stairs with Linear DP, step by step

prev2 1prev1 1

Each column is one index of dp. The column number is the step i.

prev2 dp[i - 2]
prev1 dp[i - 1]
curr the new value dp[i]

Start: prev2, prev1 = first_two = 1, 1. These are dp[0] and dp[1].

1prev2

1prev1

1 / 10

Gotchas1 of 3

The trap
Gotcha 1: Setting prev1 = curr before prev2 = prev1
Mistake
```
prev1 = curr
prev2 = prev1
```
Fix
```
prev2 = prev1
prev1 = curr
```
What happens: prev1 holds dp[i - 1] and prev2 holds dp[i - 2]. The next dp[i - 2] is the old prev1. If prev1 = curr runs first, that old value is lost. Then prev2 = prev1 copies curr, so both variables hold the same value.
Example: Climbing Stairs (LC 70): n = 5
Mistake: returns 16Fix: returns 8
Gotcha 2: Starting from values that do not match the first i
Mistake
```
prev2, prev1 = 1, 2
```
Fix
```
prev2, prev1 = 1, 1
```
What happens: prev2 and prev1 are dp[0] and dp[1], and the loop starts at i = 2. The values 1 and 2 are dp[1] and dp[2], so the first pass builds dp[3] where it should build dp[2]. Every answer is one step too far along.
Example: Climbing Stairs (LC 70): n = 5
Mistake: returns 13Fix: returns 8
Gotcha 3: Returning prev2 after the loop
Mistake
```
return prev2
```
Fix
```
return prev1
```
What happens: After the last pass, prev1 holds dp[n] and prev2 holds dp[n - 1]. Returning prev2 gives the answer for one step less.
Example: Climbing Stairs (LC 70): n = 5
Mistake: returns 5Fix: returns 8

Not this one if…

One locally best move at each index can never hurt a later one, as in Jump Game (LC 55): there are no earlier answers to weigh against each other. See Greedy
Each day you are in one of several modes (holding a stock or not) with rules for moving between them, as in Best Time to Buy and Sell Stock with Transaction Fee (LC 714): one number per index can't say which mode you are in. See State Machine DP

Deep Dive

Why dp[i] = dp[i - 1] + dp[i - 2] is correct

First decide what dp[i] means. In Climbing Stairs (LC 70), dp[i] is the number of different ways to reach step i.

Look at the last move of any path that reaches step i. The last move was 1 step, so the path came from step i - 1. Or the last move was 2 steps, so the path came from step i - 2. No other last move exists.

These two groups of paths never overlap, because their last moves differ. Together they contain every path. So the count is dp[i - 1] + dp[i - 2].

Example: dp[0] = 1 and dp[1] = 1. Then dp[2] = 2, dp[3] = 3, dp[4] = 5 and dp[5] = 8. So climbStairs(5) returns 8.

What the two rolling variables hold

A table dp of size n + 1 would work. But the formula for dp[i] reads only two earlier entries. Every older entry is never read again.

So the card keeps just two values. After step i, prev1 is dp[i] and prev2 is dp[i - 1]. This is the card's invariant.

The blueprint linear_dp starts with prev2, prev1 = first_two, which are dp[0] and dp[1]. The loop starts at i = 2. When n = 1, the loop does not run, and the function returns prev1, which is dp[1].

The function combine(prev1, prev2, i) is the only part that changes between problems. Climbing Stairs (LC 70) uses prev1 + prev2.

The cost: states times work per state

There are n states after the first two. Each state costs one combine call. Let T be the time of one call. The time is O(N * T), as the blueprint says.

For climbStairs, T = O(1), so the time is O(N). The space is O(1), because only prev1, prev2 and curr exist.

Compare this with plain recursion that calls f(n - 1) + f(n - 2). For n = 30, it makes 2,692,537 calls to return 1,346,269. The same answer takes 29 passes through the loop. The recursion repeats the same step many times. The loop computes each step once.

Answers grow fast. climbStairs(45) is 1,836,311,903. Python integers have no limit, but in a language with 32-bit integers, check the size of the answer.

Changing combine for other problems

Only first_two and combine change. The loop and the shift stay the same.

For Min Cost Climbing Stairs (LC 746), dp[i] is the least cost to reach step i. Use first_two = (0, 0) and combine = min(prev1 + cost[i - 1], prev2 + cost[i - 2]), with n = len(cost). For cost = [10, 15, 20], this returns 15. For cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1], it returns 6.

If a step needs the last three answers, as in N-th Tribonacci Number (LC 1137), this card is not enough. Use three rolling variables, with the same idea.

If the answer at i needs a choice between modes, such as holding a stock or not, one number per index is not enough. Use the State Machine DP card.

60-Second Pitch

"The last move onto step i is 1 step or 2 steps. So the number of ways to reach step i is the sum of the ways to reach step i - 1 and step i - 2. That formula reads only two earlier answers, so I keep them in prev1 and prev2 and do not build a table. I loop from step 2 to n. Each pass builds curr, then moves prev2 and prev1 forward, in that order. The time is O(N) and the space is O(1). If the step needs a different rule, such as a minimum cost, I change only the combine line."

Common Questions

Why do you keep two variables and not a full table?: The formula for dp[i] reads only dp[i - 1] and dp[i - 2]. Older entries are never read again, so storing them wastes space. Two variables give O(1) space. Keep the full table only when the problem asks for the path itself, or when a later step needs older entries.
What are the base cases for Climbing Stairs (LC 70)?: dp[0] = 1 and dp[1] = 1. There is one way to stand on step 0, which is to do nothing. There is one way to reach step 1, which is a single 1-step move. The loop starts at i = 2.
How do you change the code for Min Cost Climbing Stairs (LC 746)?: Use first_two = (0, 0), because you may start at step 0 or step 1 for free. Use curr = min(prev1 + cost[i - 1], prev2 + cost[i - 2]), with n = len(cost), and return prev1. For cost = [10, 15, 20], the answer is 15.
What if the new answer needs the last three answers?: Add a third variable and shift all three in the right order: oldest first. N-th Tribonacci Number (LC 1137) is an example. The idea is the same. The space is still O(1), because the number of variables is fixed.
What is the time and space complexity?: O(N * T) time, where T is the time of one combine call. For Climbing Stairs (LC 70), T = O(1), so the time is O(N). The space is O(1).

SWE Reasoning

Spot it

The items form a line, and you move from left to right, or step by step.
The answer at position i is built from the answers at the last one or two positions only.
The question asks for a count of ways, or the best total, to reach a position.
The brute-force recursion calls the same position many times.
Each position needs only one number to describe the situation. No mode such as "holding" or "not holding" exists.

The invariant, step by step

Before the loop, prev2 is dp[0] and prev1 is dp[1]. These come from first_two.
At step i, both prev1 and prev2 are final answers. Nothing will change them later.
curr = combine(prev1, prev2, i) builds dp[i] from those two values only.
prev2 = prev1 runs first. Now prev2 holds dp[i - 1].
prev1 = curr runs second. Now prev1 holds dp[i].
The invariant holds again for i + 1. When the loop ends, prev1 is dp[n], and the function returns it.

Traps

Wrong shift order. If prev1 = curr runs before prev2 = prev1, the old prev1 is lost. Both variables then hold curr. climbStairs(5) returns 16 instead of 8.
Wrong start values. prev2, prev1 = 1, 2 are dp[1] and dp[2], but the loop starts at i = 2. Every answer moves one step too far. climbStairs(5) returns 13 instead of 8.
Returning prev2. After the loop, prev2 is dp[n - 1]. climbStairs(5) returns 5 instead of 8.
Undefined meaning of dp[i]. If you write the formula before you decide what dp[i] means, the base cases become guesses. Write the meaning first, in one sentence.
Input of size 0 or 1. The blueprint requires n >= 1. For n = 0, return the base answer before the loop.

Practice

Canonical LeetCode:Climbing Stairs (LC 70)Min Cost Climbing Stairs (LC 746)Paint Fence (LC 276)Arithmetic Slices (LC 413)N-th Tribonacci Number (LC 1137)Minimum Sideway Jumps (LC 1824)

Theory Context•Dynamic Programming

P0EasyMental model~3 min speedrun

1D DP (Linear DP)

Grows into

Best Sightseeing Pair Kadane's Algorithm House Robber

Unlocks

Unbounded Knapsack Grid DP 0/1 Knapsack LIS State Machine DP Tree State DP Josephus Problem Digit DP

The problem

Climbing Stairs (LC 70)(opens leetcode.com)

A staircase has n steps between you and the top, and on every move you advance exactly 1 or 2 steps.

Count how many distinct sequences of moves get you all the way from the bottom to step n.

Example 1

Input:n = 2

Output:2

Two move sequences reach the top: two single steps in a row, or one double step.

Linear DP

dp[i] = the answer for the first i steps ➔ built from dp[i-1] and dp[i-2] ➔ O(1) rolling registers

Spot it when: Items come in a line and the answer at position i is built only from the answers at the last one or two positions: steps of 1 or 2, counts of ways, best totals.

Linear DP

Python

1	from typing import Callable
2
3
4	def linear_dp(n: int, first_two: tuple[int, int], combine: Callable[[int, int, int], int]) -> int:
5	"""Linear DP: dp[i] is built from dp[i - 1] and dp[i - 2], kept in two rolling variables.
6	combine(prev1, prev2, i) returns dp[i] from the two answers before it.
7	Precondition: first_two is (dp[0], dp[1]) and n >= 1.
8	T = the time of one combine call.
9	Time: O(N * T) \| Space: O(1)
10	"""
11	# prev2, prev1: dp[i - 2] and dp[i - 1], the only two answers the next one needs
12	prev2, prev1 = first_two
13	for i in range(2, n + 1):
14	# 1. Build dp[i] From The Last Two Answers:
15	# Both answers are final, so one call to combine gives dp[i] without looking further back.
16	curr = combine(prev1, prev2, i)
17
18	# 2. Roll The Window Forward:
19	# prev2 takes the old prev1 first, because prev1 is overwritten on the next line.
20	prev2 = prev1
21	prev1 = curr
22
23	return prev1

Invariant: After each step i, prev1 is dp[i] and prev2 is dp[i - 1].

See it run

Climbing Stairs with Linear DP, step by step

prev2 1prev1 1

Each column is one index of dp. The column number is the step i.

prev2 dp[i - 2]
prev1 dp[i - 1]
curr the new value dp[i]

Start: prev2, prev1 = first_two = 1, 1. These are dp[0] and dp[1].

1prev2

1prev1

1 / 10

Gotchas1 of 3

The trap
Gotcha 1: Setting prev1 = curr before prev2 = prev1
Mistake
```
prev1 = curr
prev2 = prev1
```
Fix
```
prev2 = prev1
prev1 = curr
```
What happens: prev1 holds dp[i - 1] and prev2 holds dp[i - 2]. The next dp[i - 2] is the old prev1. If prev1 = curr runs first, that old value is lost. Then prev2 = prev1 copies curr, so both variables hold the same value.
Example: Climbing Stairs (LC 70): n = 5
Mistake: returns 16Fix: returns 8
Gotcha 2: Starting from values that do not match the first i
Mistake
```
prev2, prev1 = 1, 2
```
Fix
```
prev2, prev1 = 1, 1
```
What happens: prev2 and prev1 are dp[0] and dp[1], and the loop starts at i = 2. The values 1 and 2 are dp[1] and dp[2], so the first pass builds dp[3] where it should build dp[2]. Every answer is one step too far along.
Example: Climbing Stairs (LC 70): n = 5
Mistake: returns 13Fix: returns 8
Gotcha 3: Returning prev2 after the loop
Mistake
```
return prev2
```
Fix
```
return prev1
```
What happens: After the last pass, prev1 holds dp[n] and prev2 holds dp[n - 1]. Returning prev2 gives the answer for one step less.
Example: Climbing Stairs (LC 70): n = 5
Mistake: returns 5Fix: returns 8

Not this one if…

One locally best move at each index can never hurt a later one, as in Jump Game (LC 55): there are no earlier answers to weigh against each other. See Greedy
Each day you are in one of several modes (holding a stock or not) with rules for moving between them, as in Best Time to Buy and Sell Stock with Transaction Fee (LC 714): one number per index can't say which mode you are in. See State Machine DP

Deep Dive

Why dp[i] = dp[i - 1] + dp[i - 2] is correct

First decide what dp[i] means. In Climbing Stairs (LC 70), dp[i] is the number of different ways to reach step i.

These two groups of paths never overlap, because their last moves differ. Together they contain every path. So the count is dp[i - 1] + dp[i - 2].

Example: dp[0] = 1 and dp[1] = 1. Then dp[2] = 2, dp[3] = 3, dp[4] = 5 and dp[5] = 8. So climbStairs(5) returns 8.

What the two rolling variables hold

A table dp of size n + 1 would work. But the formula for dp[i] reads only two earlier entries. Every older entry is never read again.

So the card keeps just two values. After step i, prev1 is dp[i] and prev2 is dp[i - 1]. This is the card's invariant.

The function combine(prev1, prev2, i) is the only part that changes between problems. Climbing Stairs (LC 70) uses prev1 + prev2.

The cost: states times work per state

There are n states after the first two. Each state costs one combine call. Let T be the time of one call. The time is O(N * T), as the blueprint says.

For climbStairs, T = O(1), so the time is O(N). The space is O(1), because only prev1, prev2 and curr exist.

Answers grow fast. climbStairs(45) is 1,836,311,903. Python integers have no limit, but in a language with 32-bit integers, check the size of the answer.

Changing combine for other problems

Only first_two and combine change. The loop and the shift stay the same.

If a step needs the last three answers, as in N-th Tribonacci Number (LC 1137), this card is not enough. Use three rolling variables, with the same idea.

If the answer at i needs a choice between modes, such as holding a stock or not, one number per index is not enough. Use the State Machine DP card.

60-Second Pitch

Common Questions

Why do you keep two variables and not a full table?: The formula for dp[i] reads only dp[i - 1] and dp[i - 2]. Older entries are never read again, so storing them wastes space. Two variables give O(1) space. Keep the full table only when the problem asks for the path itself, or when a later step needs older entries.
What are the base cases for Climbing Stairs (LC 70)?: dp[0] = 1 and dp[1] = 1. There is one way to stand on step 0, which is to do nothing. There is one way to reach step 1, which is a single 1-step move. The loop starts at i = 2.
How do you change the code for Min Cost Climbing Stairs (LC 746)?: Use first_two = (0, 0), because you may start at step 0 or step 1 for free. Use curr = min(prev1 + cost[i - 1], prev2 + cost[i - 2]), with n = len(cost), and return prev1. For cost = [10, 15, 20], the answer is 15.
What if the new answer needs the last three answers?: Add a third variable and shift all three in the right order: oldest first. N-th Tribonacci Number (LC 1137) is an example. The idea is the same. The space is still O(1), because the number of variables is fixed.
What is the time and space complexity?: O(N * T) time, where T is the time of one combine call. For Climbing Stairs (LC 70), T = O(1), so the time is O(N). The space is O(1).

SWE Reasoning

Spot it

The items form a line, and you move from left to right, or step by step.
The answer at position i is built from the answers at the last one or two positions only.
The question asks for a count of ways, or the best total, to reach a position.
The brute-force recursion calls the same position many times.
Each position needs only one number to describe the situation. No mode such as "holding" or "not holding" exists.

The invariant, step by step

Before the loop, prev2 is dp[0] and prev1 is dp[1]. These come from first_two.
At step i, both prev1 and prev2 are final answers. Nothing will change them later.
curr = combine(prev1, prev2, i) builds dp[i] from those two values only.
prev2 = prev1 runs first. Now prev2 holds dp[i - 1].
prev1 = curr runs second. Now prev1 holds dp[i].
The invariant holds again for i + 1. When the loop ends, prev1 is dp[n], and the function returns it.

Traps

Wrong shift order. If prev1 = curr runs before prev2 = prev1, the old prev1 is lost. Both variables then hold curr. climbStairs(5) returns 16 instead of 8.
Wrong start values. prev2, prev1 = 1, 2 are dp[1] and dp[2], but the loop starts at i = 2. Every answer moves one step too far. climbStairs(5) returns 13 instead of 8.
Returning prev2. After the loop, prev2 is dp[n - 1]. climbStairs(5) returns 5 instead of 8.
Undefined meaning of dp[i]. If you write the formula before you decide what dp[i] means, the base cases become guesses. Write the meaning first, in one sentence.
Input of size 0 or 1. The blueprint requires n >= 1. For n = 0, return the base answer before the loop.

Practice

Canonical LeetCode:Climbing Stairs (LC 70)Min Cost Climbing Stairs (LC 746)Paint Fence (LC 276)Arithmetic Slices (LC 413)N-th Tribonacci Number (LC 1137)Minimum Sideway Jumps (LC 1824)

Theory Context•Dynamic Programming

P0EasyMental model~3 min speedrun

1D DP (Linear DP)

Grows into

Best Sightseeing Pair Kadane's Algorithm House Robber

Unlocks

Unbounded Knapsack Grid DP 0/1 Knapsack LIS State Machine DP Tree State DP Josephus Problem Digit DP

The problem

Climbing Stairs (LC 70)(opens leetcode.com)

A staircase has n steps between you and the top, and on every move you advance exactly 1 or 2 steps.

Count how many distinct sequences of moves get you all the way from the bottom to step n.

Example 1

Input:n = 2

Output:2

Two move sequences reach the top: two single steps in a row, or one double step.

Linear DP

dp[i] = the answer for the first i steps ➔ built from dp[i-1] and dp[i-2] ➔ O(1) rolling registers

Spot it when: Items come in a line and the answer at position i is built only from the answers at the last one or two positions: steps of 1 or 2, counts of ways, best totals.

Linear DP

Python

1	from typing import Callable
2
3
4	def linear_dp(n: int, first_two: tuple[int, int], combine: Callable[[int, int, int], int]) -> int:
5	"""Linear DP: dp[i] is built from dp[i - 1] and dp[i - 2], kept in two rolling variables.
6	combine(prev1, prev2, i) returns dp[i] from the two answers before it.
7	Precondition: first_two is (dp[0], dp[1]) and n >= 1.
8	T = the time of one combine call.
9	Time: O(N * T) \| Space: O(1)
10	"""
11	# prev2, prev1: dp[i - 2] and dp[i - 1], the only two answers the next one needs
12	prev2, prev1 = first_two
13	for i in range(2, n + 1):
14	# 1. Build dp[i] From The Last Two Answers:
15	# Both answers are final, so one call to combine gives dp[i] without looking further back.
16	curr = combine(prev1, prev2, i)
17
18	# 2. Roll The Window Forward:
19	# prev2 takes the old prev1 first, because prev1 is overwritten on the next line.
20	prev2 = prev1
21	prev1 = curr
22
23	return prev1

Invariant: After each step i, prev1 is dp[i] and prev2 is dp[i - 1].

See it run

Climbing Stairs with Linear DP, step by step

prev2 1prev1 1

Each column is one index of dp. The column number is the step i.

prev2 dp[i - 2]
prev1 dp[i - 1]
curr the new value dp[i]

Start: prev2, prev1 = first_two = 1, 1. These are dp[0] and dp[1].

1prev2

1prev1

1 / 10

Gotchas1 of 3

The trap
Gotcha 1: Setting prev1 = curr before prev2 = prev1
Mistake
```
prev1 = curr
prev2 = prev1
```
Fix
```
prev2 = prev1
prev1 = curr
```
What happens: prev1 holds dp[i - 1] and prev2 holds dp[i - 2]. The next dp[i - 2] is the old prev1. If prev1 = curr runs first, that old value is lost. Then prev2 = prev1 copies curr, so both variables hold the same value.
Example: Climbing Stairs (LC 70): n = 5
Mistake: returns 16Fix: returns 8
Gotcha 2: Starting from values that do not match the first i
Mistake
```
prev2, prev1 = 1, 2
```
Fix
```
prev2, prev1 = 1, 1
```
What happens: prev2 and prev1 are dp[0] and dp[1], and the loop starts at i = 2. The values 1 and 2 are dp[1] and dp[2], so the first pass builds dp[3] where it should build dp[2]. Every answer is one step too far along.
Example: Climbing Stairs (LC 70): n = 5
Mistake: returns 13Fix: returns 8
Gotcha 3: Returning prev2 after the loop
Mistake
```
return prev2
```
Fix
```
return prev1
```
What happens: After the last pass, prev1 holds dp[n] and prev2 holds dp[n - 1]. Returning prev2 gives the answer for one step less.
Example: Climbing Stairs (LC 70): n = 5
Mistake: returns 5Fix: returns 8

Not this one if…

One locally best move at each index can never hurt a later one, as in Jump Game (LC 55): there are no earlier answers to weigh against each other. See Greedy
Each day you are in one of several modes (holding a stock or not) with rules for moving between them, as in Best Time to Buy and Sell Stock with Transaction Fee (LC 714): one number per index can't say which mode you are in. See State Machine DP

Deep Dive

Why dp[i] = dp[i - 1] + dp[i - 2] is correct

First decide what dp[i] means. In Climbing Stairs (LC 70), dp[i] is the number of different ways to reach step i.

These two groups of paths never overlap, because their last moves differ. Together they contain every path. So the count is dp[i - 1] + dp[i - 2].

Example: dp[0] = 1 and dp[1] = 1. Then dp[2] = 2, dp[3] = 3, dp[4] = 5 and dp[5] = 8. So climbStairs(5) returns 8.

What the two rolling variables hold

A table dp of size n + 1 would work. But the formula for dp[i] reads only two earlier entries. Every older entry is never read again.

So the card keeps just two values. After step i, prev1 is dp[i] and prev2 is dp[i - 1]. This is the card's invariant.

The function combine(prev1, prev2, i) is the only part that changes between problems. Climbing Stairs (LC 70) uses prev1 + prev2.

The cost: states times work per state

There are n states after the first two. Each state costs one combine call. Let T be the time of one call. The time is O(N * T), as the blueprint says.

For climbStairs, T = O(1), so the time is O(N). The space is O(1), because only prev1, prev2 and curr exist.

Answers grow fast. climbStairs(45) is 1,836,311,903. Python integers have no limit, but in a language with 32-bit integers, check the size of the answer.

Changing combine for other problems

Only first_two and combine change. The loop and the shift stay the same.

If a step needs the last three answers, as in N-th Tribonacci Number (LC 1137), this card is not enough. Use three rolling variables, with the same idea.

If the answer at i needs a choice between modes, such as holding a stock or not, one number per index is not enough. Use the State Machine DP card.

60-Second Pitch

Common Questions

Why do you keep two variables and not a full table?: The formula for dp[i] reads only dp[i - 1] and dp[i - 2]. Older entries are never read again, so storing them wastes space. Two variables give O(1) space. Keep the full table only when the problem asks for the path itself, or when a later step needs older entries.
What are the base cases for Climbing Stairs (LC 70)?: dp[0] = 1 and dp[1] = 1. There is one way to stand on step 0, which is to do nothing. There is one way to reach step 1, which is a single 1-step move. The loop starts at i = 2.
How do you change the code for Min Cost Climbing Stairs (LC 746)?: Use first_two = (0, 0), because you may start at step 0 or step 1 for free. Use curr = min(prev1 + cost[i - 1], prev2 + cost[i - 2]), with n = len(cost), and return prev1. For cost = [10, 15, 20], the answer is 15.
What if the new answer needs the last three answers?: Add a third variable and shift all three in the right order: oldest first. N-th Tribonacci Number (LC 1137) is an example. The idea is the same. The space is still O(1), because the number of variables is fixed.
What is the time and space complexity?: O(N * T) time, where T is the time of one combine call. For Climbing Stairs (LC 70), T = O(1), so the time is O(N). The space is O(1).

SWE Reasoning

Spot it

The items form a line, and you move from left to right, or step by step.
The answer at position i is built from the answers at the last one or two positions only.
The question asks for a count of ways, or the best total, to reach a position.
The brute-force recursion calls the same position many times.
Each position needs only one number to describe the situation. No mode such as "holding" or "not holding" exists.

The invariant, step by step

Before the loop, prev2 is dp[0] and prev1 is dp[1]. These come from first_two.
At step i, both prev1 and prev2 are final answers. Nothing will change them later.
curr = combine(prev1, prev2, i) builds dp[i] from those two values only.
prev2 = prev1 runs first. Now prev2 holds dp[i - 1].
prev1 = curr runs second. Now prev1 holds dp[i].
The invariant holds again for i + 1. When the loop ends, prev1 is dp[n], and the function returns it.

Traps

Wrong shift order. If prev1 = curr runs before prev2 = prev1, the old prev1 is lost. Both variables then hold curr. climbStairs(5) returns 16 instead of 8.
Wrong start values. prev2, prev1 = 1, 2 are dp[1] and dp[2], but the loop starts at i = 2. Every answer moves one step too far. climbStairs(5) returns 13 instead of 8.
Returning prev2. After the loop, prev2 is dp[n - 1]. climbStairs(5) returns 5 instead of 8.
Undefined meaning of dp[i]. If you write the formula before you decide what dp[i] means, the base cases become guesses. Write the meaning first, in one sentence.
Input of size 0 or 1. The blueprint requires n >= 1. For n = 0, return the base answer before the loop.

Practice

Canonical LeetCode:Climbing Stairs (LC 70)Min Cost Climbing Stairs (LC 746)Paint Fence (LC 276)Arithmetic Slices (LC 413)N-th Tribonacci Number (LC 1137)Minimum Sideway Jumps (LC 1824)

Theory Context•Dynamic Programming

P0EasyMental model~3 min speedrun

1D DP (Linear DP)

Grows into

Best Sightseeing Pair Kadane's Algorithm House Robber

Unlocks

Unbounded Knapsack Grid DP 0/1 Knapsack LIS State Machine DP Tree State DP Josephus Problem Digit DP

The problem

Climbing Stairs (LC 70)(opens leetcode.com)

A staircase has n steps between you and the top, and on every move you advance exactly 1 or 2 steps.

Count how many distinct sequences of moves get you all the way from the bottom to step n.

Example 1

Input:n = 2

Output:2

Two move sequences reach the top: two single steps in a row, or one double step.

Linear DP

dp[i] = the answer for the first i steps ➔ built from dp[i-1] and dp[i-2] ➔ O(1) rolling registers

Spot it when: Items come in a line and the answer at position i is built only from the answers at the last one or two positions: steps of 1 or 2, counts of ways, best totals.

Linear DP

Python

1	from typing import Callable
2
3
4	def linear_dp(n: int, first_two: tuple[int, int], combine: Callable[[int, int, int], int]) -> int:
5	"""Linear DP: dp[i] is built from dp[i - 1] and dp[i - 2], kept in two rolling variables.
6	combine(prev1, prev2, i) returns dp[i] from the two answers before it.
7	Precondition: first_two is (dp[0], dp[1]) and n >= 1.
8	T = the time of one combine call.
9	Time: O(N * T) \| Space: O(1)
10	"""
11	# prev2, prev1: dp[i - 2] and dp[i - 1], the only two answers the next one needs
12	prev2, prev1 = first_two
13	for i in range(2, n + 1):
14	# 1. Build dp[i] From The Last Two Answers:
15	# Both answers are final, so one call to combine gives dp[i] without looking further back.
16	curr = combine(prev1, prev2, i)
17
18	# 2. Roll The Window Forward:
19	# prev2 takes the old prev1 first, because prev1 is overwritten on the next line.
20	prev2 = prev1
21	prev1 = curr
22
23	return prev1

Invariant: After each step i, prev1 is dp[i] and prev2 is dp[i - 1].

See it run

Climbing Stairs with Linear DP, step by step

prev2 1prev1 1

Each column is one index of dp. The column number is the step i.

prev2 dp[i - 2]
prev1 dp[i - 1]
curr the new value dp[i]

Start: prev2, prev1 = first_two = 1, 1. These are dp[0] and dp[1].

1prev2

1prev1

1 / 10

Gotchas1 of 3

The trap
Gotcha 1: Setting prev1 = curr before prev2 = prev1
Mistake
```
prev1 = curr
prev2 = prev1
```
Fix
```
prev2 = prev1
prev1 = curr
```
What happens: prev1 holds dp[i - 1] and prev2 holds dp[i - 2]. The next dp[i - 2] is the old prev1. If prev1 = curr runs first, that old value is lost. Then prev2 = prev1 copies curr, so both variables hold the same value.
Example: Climbing Stairs (LC 70): n = 5
Mistake: returns 16Fix: returns 8
Gotcha 2: Starting from values that do not match the first i
Mistake
```
prev2, prev1 = 1, 2
```
Fix
```
prev2, prev1 = 1, 1
```
What happens: prev2 and prev1 are dp[0] and dp[1], and the loop starts at i = 2. The values 1 and 2 are dp[1] and dp[2], so the first pass builds dp[3] where it should build dp[2]. Every answer is one step too far along.
Example: Climbing Stairs (LC 70): n = 5
Mistake: returns 13Fix: returns 8
Gotcha 3: Returning prev2 after the loop
Mistake
```
return prev2
```
Fix
```
return prev1
```
What happens: After the last pass, prev1 holds dp[n] and prev2 holds dp[n - 1]. Returning prev2 gives the answer for one step less.
Example: Climbing Stairs (LC 70): n = 5
Mistake: returns 5Fix: returns 8

Not this one if…

One locally best move at each index can never hurt a later one, as in Jump Game (LC 55): there are no earlier answers to weigh against each other. See Greedy
Each day you are in one of several modes (holding a stock or not) with rules for moving between them, as in Best Time to Buy and Sell Stock with Transaction Fee (LC 714): one number per index can't say which mode you are in. See State Machine DP

Deep Dive

Why dp[i] = dp[i - 1] + dp[i - 2] is correct

First decide what dp[i] means. In Climbing Stairs (LC 70), dp[i] is the number of different ways to reach step i.

These two groups of paths never overlap, because their last moves differ. Together they contain every path. So the count is dp[i - 1] + dp[i - 2].

Example: dp[0] = 1 and dp[1] = 1. Then dp[2] = 2, dp[3] = 3, dp[4] = 5 and dp[5] = 8. So climbStairs(5) returns 8.

What the two rolling variables hold

A table dp of size n + 1 would work. But the formula for dp[i] reads only two earlier entries. Every older entry is never read again.

So the card keeps just two values. After step i, prev1 is dp[i] and prev2 is dp[i - 1]. This is the card's invariant.

The function combine(prev1, prev2, i) is the only part that changes between problems. Climbing Stairs (LC 70) uses prev1 + prev2.

The cost: states times work per state

There are n states after the first two. Each state costs one combine call. Let T be the time of one call. The time is O(N * T), as the blueprint says.

For climbStairs, T = O(1), so the time is O(N). The space is O(1), because only prev1, prev2 and curr exist.

Answers grow fast. climbStairs(45) is 1,836,311,903. Python integers have no limit, but in a language with 32-bit integers, check the size of the answer.

Changing combine for other problems

Only first_two and combine change. The loop and the shift stay the same.

If a step needs the last three answers, as in N-th Tribonacci Number (LC 1137), this card is not enough. Use three rolling variables, with the same idea.

If the answer at i needs a choice between modes, such as holding a stock or not, one number per index is not enough. Use the State Machine DP card.

60-Second Pitch

Common Questions

Why do you keep two variables and not a full table?: The formula for dp[i] reads only dp[i - 1] and dp[i - 2]. Older entries are never read again, so storing them wastes space. Two variables give O(1) space. Keep the full table only when the problem asks for the path itself, or when a later step needs older entries.
What are the base cases for Climbing Stairs (LC 70)?: dp[0] = 1 and dp[1] = 1. There is one way to stand on step 0, which is to do nothing. There is one way to reach step 1, which is a single 1-step move. The loop starts at i = 2.
How do you change the code for Min Cost Climbing Stairs (LC 746)?: Use first_two = (0, 0), because you may start at step 0 or step 1 for free. Use curr = min(prev1 + cost[i - 1], prev2 + cost[i - 2]), with n = len(cost), and return prev1. For cost = [10, 15, 20], the answer is 15.
What if the new answer needs the last three answers?: Add a third variable and shift all three in the right order: oldest first. N-th Tribonacci Number (LC 1137) is an example. The idea is the same. The space is still O(1), because the number of variables is fixed.
What is the time and space complexity?: O(N * T) time, where T is the time of one combine call. For Climbing Stairs (LC 70), T = O(1), so the time is O(N). The space is O(1).

SWE Reasoning

Spot it

The items form a line, and you move from left to right, or step by step.
The answer at position i is built from the answers at the last one or two positions only.
The question asks for a count of ways, or the best total, to reach a position.
The brute-force recursion calls the same position many times.
Each position needs only one number to describe the situation. No mode such as "holding" or "not holding" exists.

The invariant, step by step

Before the loop, prev2 is dp[0] and prev1 is dp[1]. These come from first_two.
At step i, both prev1 and prev2 are final answers. Nothing will change them later.
curr = combine(prev1, prev2, i) builds dp[i] from those two values only.
prev2 = prev1 runs first. Now prev2 holds dp[i - 1].
prev1 = curr runs second. Now prev1 holds dp[i].
The invariant holds again for i + 1. When the loop ends, prev1 is dp[n], and the function returns it.

Traps

Wrong shift order. If prev1 = curr runs before prev2 = prev1, the old prev1 is lost. Both variables then hold curr. climbStairs(5) returns 16 instead of 8.
Wrong start values. prev2, prev1 = 1, 2 are dp[1] and dp[2], but the loop starts at i = 2. Every answer moves one step too far. climbStairs(5) returns 13 instead of 8.
Returning prev2. After the loop, prev2 is dp[n - 1]. climbStairs(5) returns 5 instead of 8.
Undefined meaning of dp[i]. If you write the formula before you decide what dp[i] means, the base cases become guesses. Write the meaning first, in one sentence.
Input of size 0 or 1. The blueprint requires n >= 1. For n = 0, return the base answer before the loop.

Practice

Canonical LeetCode:Climbing Stairs (LC 70)Min Cost Climbing Stairs (LC 746)Paint Fence (LC 276)Arithmetic Slices (LC 413)N-th Tribonacci Number (LC 1137)Minimum Sideway Jumps (LC 1824)