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 Grid DP, which you haven’t finished yet.

P2MediumMental model~5 min speedrun

Probability DP (Knight Probability, New 21 Game)

The problem

Knight Probability in Chessboard (LC 688)(opens leetcode.com)

A knight starts on the square (row, column) of an n x n chessboard and makes exactly k moves. A knight move goes two squares in one direction and one square in the other, so from most squares it has 8 possible moves.

At every move, the knight picks one of its 8 moves with equal chance, even when that move would take it off the board. Once the knight is off the board, it stays off.

Return the probability that the knight is still on the board after it has made k moves.

Example 1

Input:n = 3, k = 2, row = 0, column = 0

Output:0.0625

From the corner, two of the eight moves stay on the board, to (1, 2) and (2, 1). From each of those, two of the eight moves stay on again. So the probability is 2/8 * 2/8 = 0.0625.

Probability DP

state probability dp[s] ➔ spread over the equally likely moves each step ➔ total on the states that count

Spot it when: You want the chance that a random process ends in a certain way: equally likely moves on a board, random draws toward a score, or a walk that can be lost for good.

Probability DP

Python

1	def knight_probability(n: int, k: int, row: int, column: int) -> float:
2	"""Probability DP: spread each square's probability over the 8 knight moves, k times, and total what stays on the board.
3	Time: O(K * N^2) \| Space: O(N^2)
4	"""
5	moves = [(1, 2), (2, 1), (2, -1), (1, -2), (-1, -2), (-2, -1), (-2, 1), (-1, 2)]
6	# dp: dp[r][c] is the probability that the knight stands on (r, c) after the moves made so far, never having left the board
7	dp = [[0.0] * n for _ in range(n)]
8	dp[row][column] = 1.0
9
10	for _ in range(k):
11	nxt = [[0.0] * n for _ in range(n)]
12	for r in range(n):
13	for c in range(n):
14	# 1. Spread Each Square's Probability Over The 8 Moves:
15	# Each move has chance 1/8, so a square passes dp[r][c] / 8 to every target that is still on the board.
16	for dr, dc in moves:
17	nr, nc = r + dr, c + dc
18	if 0 <= nr < n and 0 <= nc < n:
19	nxt[nr][nc] += dp[r][c] / 8
20	# 2. Replace The Board With The New Step:
21	# The share that fell off the board is added nowhere, so it is gone for every later step.
22	dp = nxt
23
24	# 3. Add Up What Is Left On The Board:
25	# Each square holds the probability of being there after k moves without leaving, so their total is the answer.
26	return sum(sum(line) for line in dp)

Invariant: After each step, dp[r][c] is the probability that the knight is on (r, c) after the moves made so far without having left the board.

Give every state the probability of being there after the steps made so far, and build the next step by passing each state's share to the states it can move to: with 8 equally likely moves, a square passes dp[r][c] / 8 to each target. A target off the board adds nothing, so that share is lost for good. Build the new step in a fresh board nxt and replace dp after the pass, so a share is never passed on twice in one step. The trap is the chance of each move: pass dp[r][c] / 8, not dp[r][c], or the table counts paths and the answer is far above 1.

See it run

Probability DP on a 3 x 3 board, k = 2, step by step

moves 0 of 2on board 1

The top rows are dp, the board before the move. The bottom rows are nxt, the board after it. Each row is a board row r and each column is a board column c.

knight the starting square, with probability 1
from a square that passes its probability on
receive a square in nxt that receives a share

dp[0][0] = 1.0, because the knight is certainly on its starting square. Every other square holds 0.

dp r0

1knight

dp r1

dp r2

nxt r0

nxt r1

nxt r2

1 / 9

Gotchas1 of 3

The trap
Gotcha 1: Passing the whole probability instead of one eighth
Mistake
```
nxt[nr][nc] += dp[r][c]
```
Fix
```
nxt[nr][nc] += dp[r][c] / 8
```
What happens: A knight picks one of its 8 moves with equal chance, so each target receives one eighth of the square's probability. Without the division, each target receives the whole probability. The table then counts paths, and the answer is far above 1.
Example: n = 3, k = 2, row = 0, column = 0
Mistake: returns 4.0Fix: returns 0.0625
Gotcha 2: Updating dp in place instead of building nxt
Mistake
```
dp[nr][nc] += dp[r][c] / 8
```
Fix
```
nxt[nr][nc] += dp[r][c] / 8
```
What happens: One step must read the board before the move and write the board after it. Writing into dp while reading dp lets a square pass on a share it has just received, so the knight moves twice in one step, and the total probability is too large.
Example: n = 3, k = 2, row = 0, column = 0
Mistake: returns 1.7191162109375Fix: returns 0.0625
Gotcha 3: Wrapping a move around the edge of the board
Mistake
```
nr, nc = (r + dr) % n, (c + dc) % n
```
Fix
```
nr, nc = r + dr, c + dc
```
What happens: A move off the board ends the walk: the knight stays off, and its share is lost. Taking % n brings the knight back onto the other side, so no share is ever lost and the answer is always 1.0.
Example: n = 3, k = 2, row = 0, column = 0
Mistake: returns 1.0Fix: returns 0.0625

Not this one if…

You count the number of ways, not a chance, as in Climbing Stairs (LC 70): every way counts as 1 and the counts are added, with no equal-chance weight to carry. See Linear DP
You count the paths from one corner to another on a grid, as in Unique Paths (LC 62): each cell adds the cell above and the cell to the left, and there is no random move to weight. See Grid DP

Deep Dive

The state is a share of probability, not a count

A probability DP does not ask how many ways reach a state. It asks how much probability is in that state after the steps made so far. In knight_probability, dp[r][c] is the probability that the knight stands on (r, c), and it has never left the board.

At the start, dp[row][column] = 1.0, because the knight is certainly on the starting square. All other squares hold 0.0. The total over the board is 1.0.

The model works because the steps are independent. The chance of the next move does not depend on how the knight arrived at its square. So the square's probability is enough, and the path is not needed.

One step spreads each share equally

The knight has 8 moves, and each has the chance 1/8. A square that holds dp[r][c] passes dp[r][c] / 8 to each of its 8 targets. If a target is on the board, nxt[nr][nc] receives that amount.

A target can receive from several squares, so the code uses +=. The result is the sum over all squares that can reach it.

Example: n = 3, start (0, 0). Of the 8 moves, only (1, 2) and (2, 1) stay on the board. So after one step, dp[1][2] = 1/8 and dp[2][1] = 1/8. The other 6/8 are off the board.

A share that leaves the board is lost for good

When a target is off the board, the code adds nothing to nxt. That share is not moved to another square. It is simply missing from the next board, and no later step can bring it back.

So the total of dp is the probability that the knight is still on the board, and it can only stay equal or become smaller after each step. In the example above, the total is 1 at the start and 1/4 after one step.

Second step on the same board: from (1, 2) the move to (0, 0) is on the board, and from (2, 1) the move to (0, 0) also is. The squares (1, 2) and (2, 1) also reach (0, 2) and (2, 0). The result is dp[0][0] = 1/32 and dp[0][2] = dp[2][0] = 1/64. The answer for k = 2 is the total, 1/16 = 0.0625.

A brute force agrees. Of the 64 paths of two moves, exactly 4 stay on the board, and 4 / 64 = 1/16.

Why the table is rebuilt each step

A step reads the board before the move and writes the board after the move. These are two different boards, so the code builds a fresh nxt and then sets dp = nxt.

If the code wrote into dp while it reads dp, a square could pass on a share that it received in the same step. That share would then move twice in one step.

The cost, and the same idea in other problems

There are N^2 squares, 8 moves each, and K steps. The time is O(K * N^2), with the factor 8 as a constant. The space is O(N^2), because only dp and nxt exist at one time. LeetCode limits n to 25 and k to 100, so the run is at most 500,000 move checks.

In New 21 Game (LC 837), the state is the score, and dp[i] is the probability of reaching exactly score i. A draw gives each value from 1 to maxPts the chance 1/maxPts, so dp[i] is the sum of the dp[j] before it, divided by maxPts. Scores of k or more stop the game. The answer is the total over the stopped scores that are at most n.

In Soup Servings (LC 808), the state is the pair of soup amounts, and each of four serving choices has the chance 1/4. The answer adds the probability that soup A runs out first, plus half of the probability that both run out together. For n = 50 this gives 0.625, and for n = 100 it gives 0.71875.

60-Second Pitch

"I keep the probability that the knight is on each square after the moves made so far. At the start, the starting square holds 1.0. One move gives each of the 8 targets one eighth of the square's probability. I add it only if the target is on the board. A share that leaves the board is added nowhere, so it is lost. I write the new step into a fresh board nxt, so no share moves twice in one step. After k steps, the total over the board is the answer. The time is O(K * N^2) with 8 moves as a constant, and the space is O(N^2)."

Common Questions

Why do you divide by 8, and not count paths?: Each of the 8 moves has the chance 1/8, and the chances of the steps multiply. A square that holds probability p gives p / 8 to each target. If you do not divide, the table counts paths, and the total can be larger than 1. A probability can never be larger than 1.
Why is the lost share not added anywhere?: The question asks for the chance of staying on the board for all k moves. A knight that leaves the board has failed, and it cannot return in a later move. So its share is dropped, and the final total is exactly the chance of success.
What is the time and space complexity of knight_probability?: O(K * N^2) time and O(N^2) space. Each of the K steps visits N^2 squares and tries 8 moves, and 8 is a constant. The space holds dp and nxt, and each has N^2 entries.
How does New 21 Game (LC 837) use the same idea?: The state is the score. dp[i] is the probability of reaching score i, and each draw from 1 to maxPts has the chance 1/maxPts. So dp[i] is the sum of the previous maxPts values below k, divided by maxPts. A running window sum keeps this at O(N) time. The answer is the total of dp[i] for k <= i <= n.
Could you use recursion with memoization instead of a table?: Yes, but it runs in the other direction. A function f(steps_left, r, c) returns the chance of surviving from (r, c) for the rest of the steps, and it averages the 8 targets. The time is the same, O(K * N^2). The table version moves forward and avoids the recursion stack, which is why it is common in interviews.

SWE Reasoning

Spot it

The question asks for a chance, an expected fraction or a probability, not for a count or a best value.
Each step has equally likely random choices, such as the 8 knight moves, a die roll or a random draw.
The next step depends only on the current state, and the state space is small, such as N^2 squares or the scores up to n.
A random walk can end early, for example by leaving a board or reaching a score, and you want the chance of a certain end.
The brute force lists all 8^k paths. That grows too fast, but many paths reach the same square.

The invariant, step by step

dp starts with dp[row][column] = 1.0. The knight is certainly there, and every other square has 0.0.
A step begins with a fresh board nxt filled with 0.0.
For every square (r, c), the code visits each of the 8 moves and computes the target (nr, nc).
If the target is on the board, it adds dp[r][c] / 8 to nxt[nr][nc]. If the target is off the board, it adds nothing.
After all squares are done, dp = nxt. Now dp[r][c] is the probability that the knight is on (r, c) after one more move, having stayed on the board.
This repeats k times. A share that left the board is in no square, so it does not return.
The answer is sum(sum(line) for line in dp), the probability of being on the board after k moves.

Traps

Passing the whole probability. Without / 8, the table counts paths. For n = 3 and k = 2 from (0, 0), the result is 4.0 instead of 0.0625. A probability above 1 is a sign of this mistake.
Updating dp in place. A square passes on a share it has just received, so a knight moves twice in one step. The result is 1.7191162109375 instead of 0.0625 in the same example.
Wrapping around the edge. With (r + dr) % n, a share that should leave the board returns on the other side. No share is ever lost and the result is 1.0. Test 0 <= nr < n instead.
Asking for the wrong total. If the question wants the chance of being on one square, return that square. If it asks for the chance of staying on the board, return the total. Read the question before the last line.
Floating-point error. The values are fractions that need many binary digits. LeetCode accepts a small error, so use float. If an exact answer is required, use fractions.Fraction.

Practice

Canonical LeetCode:Knight Probability in Chessboard (LC 688)New 21 Game (LC 837)Soup Servings (LC 808)

Theory Context•Dynamic Programming

Builds on Grid DP, which you haven’t finished yet.

P2MediumMental model~5 min speedrun

Probability DP (Knight Probability, New 21 Game)

The problem

Knight Probability in Chessboard (LC 688)(opens leetcode.com)

At every move, the knight picks one of its 8 moves with equal chance, even when that move would take it off the board. Once the knight is off the board, it stays off.

Return the probability that the knight is still on the board after it has made k moves.

Example 1

Input:n = 3, k = 2, row = 0, column = 0

Output:0.0625

From the corner, two of the eight moves stay on the board, to (1, 2) and (2, 1). From each of those, two of the eight moves stay on again. So the probability is 2/8 * 2/8 = 0.0625.

Probability DP

state probability dp[s] ➔ spread over the equally likely moves each step ➔ total on the states that count

Spot it when: You want the chance that a random process ends in a certain way: equally likely moves on a board, random draws toward a score, or a walk that can be lost for good.

Probability DP

Python

1	def knight_probability(n: int, k: int, row: int, column: int) -> float:
2	"""Probability DP: spread each square's probability over the 8 knight moves, k times, and total what stays on the board.
3	Time: O(K * N^2) \| Space: O(N^2)
4	"""
5	moves = [(1, 2), (2, 1), (2, -1), (1, -2), (-1, -2), (-2, -1), (-2, 1), (-1, 2)]
6	# dp: dp[r][c] is the probability that the knight stands on (r, c) after the moves made so far, never having left the board
7	dp = [[0.0] * n for _ in range(n)]
8	dp[row][column] = 1.0
9
10	for _ in range(k):
11	nxt = [[0.0] * n for _ in range(n)]
12	for r in range(n):
13	for c in range(n):
14	# 1. Spread Each Square's Probability Over The 8 Moves:
15	# Each move has chance 1/8, so a square passes dp[r][c] / 8 to every target that is still on the board.
16	for dr, dc in moves:
17	nr, nc = r + dr, c + dc
18	if 0 <= nr < n and 0 <= nc < n:
19	nxt[nr][nc] += dp[r][c] / 8
20	# 2. Replace The Board With The New Step:
21	# The share that fell off the board is added nowhere, so it is gone for every later step.
22	dp = nxt
23
24	# 3. Add Up What Is Left On The Board:
25	# Each square holds the probability of being there after k moves without leaving, so their total is the answer.
26	return sum(sum(line) for line in dp)

Invariant: After each step, dp[r][c] is the probability that the knight is on (r, c) after the moves made so far without having left the board.

See it run

Probability DP on a 3 x 3 board, k = 2, step by step

moves 0 of 2on board 1

The top rows are dp, the board before the move. The bottom rows are nxt, the board after it. Each row is a board row r and each column is a board column c.

knight the starting square, with probability 1
from a square that passes its probability on
receive a square in nxt that receives a share

dp[0][0] = 1.0, because the knight is certainly on its starting square. Every other square holds 0.

dp r0

1knight

dp r1

dp r2

nxt r0

nxt r1

nxt r2

1 / 9

Gotchas1 of 3

The trap
Gotcha 1: Passing the whole probability instead of one eighth
Mistake
```
nxt[nr][nc] += dp[r][c]
```
Fix
```
nxt[nr][nc] += dp[r][c] / 8
```
What happens: A knight picks one of its 8 moves with equal chance, so each target receives one eighth of the square's probability. Without the division, each target receives the whole probability. The table then counts paths, and the answer is far above 1.
Example: n = 3, k = 2, row = 0, column = 0
Mistake: returns 4.0Fix: returns 0.0625
Gotcha 2: Updating dp in place instead of building nxt
Mistake
```
dp[nr][nc] += dp[r][c] / 8
```
Fix
```
nxt[nr][nc] += dp[r][c] / 8
```
What happens: One step must read the board before the move and write the board after it. Writing into dp while reading dp lets a square pass on a share it has just received, so the knight moves twice in one step, and the total probability is too large.
Example: n = 3, k = 2, row = 0, column = 0
Mistake: returns 1.7191162109375Fix: returns 0.0625
Gotcha 3: Wrapping a move around the edge of the board
Mistake
```
nr, nc = (r + dr) % n, (c + dc) % n
```
Fix
```
nr, nc = r + dr, c + dc
```
What happens: A move off the board ends the walk: the knight stays off, and its share is lost. Taking % n brings the knight back onto the other side, so no share is ever lost and the answer is always 1.0.
Example: n = 3, k = 2, row = 0, column = 0
Mistake: returns 1.0Fix: returns 0.0625

Not this one if…

You count the number of ways, not a chance, as in Climbing Stairs (LC 70): every way counts as 1 and the counts are added, with no equal-chance weight to carry. See Linear DP
You count the paths from one corner to another on a grid, as in Unique Paths (LC 62): each cell adds the cell above and the cell to the left, and there is no random move to weight. See Grid DP

Deep Dive

The state is a share of probability, not a count

At the start, dp[row][column] = 1.0, because the knight is certainly on the starting square. All other squares hold 0.0. The total over the board is 1.0.

One step spreads each share equally

The knight has 8 moves, and each has the chance 1/8. A square that holds dp[r][c] passes dp[r][c] / 8 to each of its 8 targets. If a target is on the board, nxt[nr][nc] receives that amount.

A target can receive from several squares, so the code uses +=. The result is the sum over all squares that can reach it.

Example: n = 3, start (0, 0). Of the 8 moves, only (1, 2) and (2, 1) stay on the board. So after one step, dp[1][2] = 1/8 and dp[2][1] = 1/8. The other 6/8 are off the board.

A share that leaves the board is lost for good

When a target is off the board, the code adds nothing to nxt. That share is not moved to another square. It is simply missing from the next board, and no later step can bring it back.

A brute force agrees. Of the 64 paths of two moves, exactly 4 stay on the board, and 4 / 64 = 1/16.

Why the table is rebuilt each step

A step reads the board before the move and writes the board after the move. These are two different boards, so the code builds a fresh nxt and then sets dp = nxt.

If the code wrote into dp while it reads dp, a square could pass on a share that it received in the same step. That share would then move twice in one step.

The cost, and the same idea in other problems

60-Second Pitch

Common Questions

Why do you divide by 8, and not count paths?: Each of the 8 moves has the chance 1/8, and the chances of the steps multiply. A square that holds probability p gives p / 8 to each target. If you do not divide, the table counts paths, and the total can be larger than 1. A probability can never be larger than 1.
Why is the lost share not added anywhere?: The question asks for the chance of staying on the board for all k moves. A knight that leaves the board has failed, and it cannot return in a later move. So its share is dropped, and the final total is exactly the chance of success.
What is the time and space complexity of knight_probability?: O(K * N^2) time and O(N^2) space. Each of the K steps visits N^2 squares and tries 8 moves, and 8 is a constant. The space holds dp and nxt, and each has N^2 entries.
How does New 21 Game (LC 837) use the same idea?: The state is the score. dp[i] is the probability of reaching score i, and each draw from 1 to maxPts has the chance 1/maxPts. So dp[i] is the sum of the previous maxPts values below k, divided by maxPts. A running window sum keeps this at O(N) time. The answer is the total of dp[i] for k <= i <= n.
Could you use recursion with memoization instead of a table?: Yes, but it runs in the other direction. A function f(steps_left, r, c) returns the chance of surviving from (r, c) for the rest of the steps, and it averages the 8 targets. The time is the same, O(K * N^2). The table version moves forward and avoids the recursion stack, which is why it is common in interviews.

SWE Reasoning

Spot it

The question asks for a chance, an expected fraction or a probability, not for a count or a best value.
Each step has equally likely random choices, such as the 8 knight moves, a die roll or a random draw.
The next step depends only on the current state, and the state space is small, such as N^2 squares or the scores up to n.
A random walk can end early, for example by leaving a board or reaching a score, and you want the chance of a certain end.
The brute force lists all 8^k paths. That grows too fast, but many paths reach the same square.

The invariant, step by step

dp starts with dp[row][column] = 1.0. The knight is certainly there, and every other square has 0.0.
A step begins with a fresh board nxt filled with 0.0.
For every square (r, c), the code visits each of the 8 moves and computes the target (nr, nc).
If the target is on the board, it adds dp[r][c] / 8 to nxt[nr][nc]. If the target is off the board, it adds nothing.
After all squares are done, dp = nxt. Now dp[r][c] is the probability that the knight is on (r, c) after one more move, having stayed on the board.
This repeats k times. A share that left the board is in no square, so it does not return.
The answer is sum(sum(line) for line in dp), the probability of being on the board after k moves.

Traps

Passing the whole probability. Without / 8, the table counts paths. For n = 3 and k = 2 from (0, 0), the result is 4.0 instead of 0.0625. A probability above 1 is a sign of this mistake.
Updating dp in place. A square passes on a share it has just received, so a knight moves twice in one step. The result is 1.7191162109375 instead of 0.0625 in the same example.
Wrapping around the edge. With (r + dr) % n, a share that should leave the board returns on the other side. No share is ever lost and the result is 1.0. Test 0 <= nr < n instead.
Asking for the wrong total. If the question wants the chance of being on one square, return that square. If it asks for the chance of staying on the board, return the total. Read the question before the last line.
Floating-point error. The values are fractions that need many binary digits. LeetCode accepts a small error, so use float. If an exact answer is required, use fractions.Fraction.

Practice

Canonical LeetCode:Knight Probability in Chessboard (LC 688)New 21 Game (LC 837)Soup Servings (LC 808)

Theory Context•Dynamic Programming

Builds on Grid DP, which you haven’t finished yet.

P2MediumMental model~5 min speedrun

Probability DP (Knight Probability, New 21 Game)

The problem

Knight Probability in Chessboard (LC 688)(opens leetcode.com)

At every move, the knight picks one of its 8 moves with equal chance, even when that move would take it off the board. Once the knight is off the board, it stays off.

Return the probability that the knight is still on the board after it has made k moves.

Example 1

Input:n = 3, k = 2, row = 0, column = 0

Output:0.0625

From the corner, two of the eight moves stay on the board, to (1, 2) and (2, 1). From each of those, two of the eight moves stay on again. So the probability is 2/8 * 2/8 = 0.0625.

Probability DP

state probability dp[s] ➔ spread over the equally likely moves each step ➔ total on the states that count

Spot it when: You want the chance that a random process ends in a certain way: equally likely moves on a board, random draws toward a score, or a walk that can be lost for good.

Probability DP

Python

1	def knight_probability(n: int, k: int, row: int, column: int) -> float:
2	"""Probability DP: spread each square's probability over the 8 knight moves, k times, and total what stays on the board.
3	Time: O(K * N^2) \| Space: O(N^2)
4	"""
5	moves = [(1, 2), (2, 1), (2, -1), (1, -2), (-1, -2), (-2, -1), (-2, 1), (-1, 2)]
6	# dp: dp[r][c] is the probability that the knight stands on (r, c) after the moves made so far, never having left the board
7	dp = [[0.0] * n for _ in range(n)]
8	dp[row][column] = 1.0
9
10	for _ in range(k):
11	nxt = [[0.0] * n for _ in range(n)]
12	for r in range(n):
13	for c in range(n):
14	# 1. Spread Each Square's Probability Over The 8 Moves:
15	# Each move has chance 1/8, so a square passes dp[r][c] / 8 to every target that is still on the board.
16	for dr, dc in moves:
17	nr, nc = r + dr, c + dc
18	if 0 <= nr < n and 0 <= nc < n:
19	nxt[nr][nc] += dp[r][c] / 8
20	# 2. Replace The Board With The New Step:
21	# The share that fell off the board is added nowhere, so it is gone for every later step.
22	dp = nxt
23
24	# 3. Add Up What Is Left On The Board:
25	# Each square holds the probability of being there after k moves without leaving, so their total is the answer.
26	return sum(sum(line) for line in dp)

Invariant: After each step, dp[r][c] is the probability that the knight is on (r, c) after the moves made so far without having left the board.

See it run

Probability DP on a 3 x 3 board, k = 2, step by step

moves 0 of 2on board 1

The top rows are dp, the board before the move. The bottom rows are nxt, the board after it. Each row is a board row r and each column is a board column c.

knight the starting square, with probability 1
from a square that passes its probability on
receive a square in nxt that receives a share

dp[0][0] = 1.0, because the knight is certainly on its starting square. Every other square holds 0.

dp r0

1knight

dp r1

dp r2

nxt r0

nxt r1

nxt r2

1 / 9

Gotchas1 of 3

The trap
Gotcha 1: Passing the whole probability instead of one eighth
Mistake
```
nxt[nr][nc] += dp[r][c]
```
Fix
```
nxt[nr][nc] += dp[r][c] / 8
```
What happens: A knight picks one of its 8 moves with equal chance, so each target receives one eighth of the square's probability. Without the division, each target receives the whole probability. The table then counts paths, and the answer is far above 1.
Example: n = 3, k = 2, row = 0, column = 0
Mistake: returns 4.0Fix: returns 0.0625
Gotcha 2: Updating dp in place instead of building nxt
Mistake
```
dp[nr][nc] += dp[r][c] / 8
```
Fix
```
nxt[nr][nc] += dp[r][c] / 8
```
What happens: One step must read the board before the move and write the board after it. Writing into dp while reading dp lets a square pass on a share it has just received, so the knight moves twice in one step, and the total probability is too large.
Example: n = 3, k = 2, row = 0, column = 0
Mistake: returns 1.7191162109375Fix: returns 0.0625
Gotcha 3: Wrapping a move around the edge of the board
Mistake
```
nr, nc = (r + dr) % n, (c + dc) % n
```
Fix
```
nr, nc = r + dr, c + dc
```
What happens: A move off the board ends the walk: the knight stays off, and its share is lost. Taking % n brings the knight back onto the other side, so no share is ever lost and the answer is always 1.0.
Example: n = 3, k = 2, row = 0, column = 0
Mistake: returns 1.0Fix: returns 0.0625

Not this one if…

You count the number of ways, not a chance, as in Climbing Stairs (LC 70): every way counts as 1 and the counts are added, with no equal-chance weight to carry. See Linear DP
You count the paths from one corner to another on a grid, as in Unique Paths (LC 62): each cell adds the cell above and the cell to the left, and there is no random move to weight. See Grid DP

Deep Dive

The state is a share of probability, not a count

At the start, dp[row][column] = 1.0, because the knight is certainly on the starting square. All other squares hold 0.0. The total over the board is 1.0.

One step spreads each share equally

The knight has 8 moves, and each has the chance 1/8. A square that holds dp[r][c] passes dp[r][c] / 8 to each of its 8 targets. If a target is on the board, nxt[nr][nc] receives that amount.

A target can receive from several squares, so the code uses +=. The result is the sum over all squares that can reach it.

Example: n = 3, start (0, 0). Of the 8 moves, only (1, 2) and (2, 1) stay on the board. So after one step, dp[1][2] = 1/8 and dp[2][1] = 1/8. The other 6/8 are off the board.

A share that leaves the board is lost for good

When a target is off the board, the code adds nothing to nxt. That share is not moved to another square. It is simply missing from the next board, and no later step can bring it back.

A brute force agrees. Of the 64 paths of two moves, exactly 4 stay on the board, and 4 / 64 = 1/16.

Why the table is rebuilt each step

A step reads the board before the move and writes the board after the move. These are two different boards, so the code builds a fresh nxt and then sets dp = nxt.

If the code wrote into dp while it reads dp, a square could pass on a share that it received in the same step. That share would then move twice in one step.

The cost, and the same idea in other problems

60-Second Pitch

Common Questions

Why do you divide by 8, and not count paths?: Each of the 8 moves has the chance 1/8, and the chances of the steps multiply. A square that holds probability p gives p / 8 to each target. If you do not divide, the table counts paths, and the total can be larger than 1. A probability can never be larger than 1.
Why is the lost share not added anywhere?: The question asks for the chance of staying on the board for all k moves. A knight that leaves the board has failed, and it cannot return in a later move. So its share is dropped, and the final total is exactly the chance of success.
What is the time and space complexity of knight_probability?: O(K * N^2) time and O(N^2) space. Each of the K steps visits N^2 squares and tries 8 moves, and 8 is a constant. The space holds dp and nxt, and each has N^2 entries.
How does New 21 Game (LC 837) use the same idea?: The state is the score. dp[i] is the probability of reaching score i, and each draw from 1 to maxPts has the chance 1/maxPts. So dp[i] is the sum of the previous maxPts values below k, divided by maxPts. A running window sum keeps this at O(N) time. The answer is the total of dp[i] for k <= i <= n.
Could you use recursion with memoization instead of a table?: Yes, but it runs in the other direction. A function f(steps_left, r, c) returns the chance of surviving from (r, c) for the rest of the steps, and it averages the 8 targets. The time is the same, O(K * N^2). The table version moves forward and avoids the recursion stack, which is why it is common in interviews.

SWE Reasoning

Spot it

The question asks for a chance, an expected fraction or a probability, not for a count or a best value.
Each step has equally likely random choices, such as the 8 knight moves, a die roll or a random draw.
The next step depends only on the current state, and the state space is small, such as N^2 squares or the scores up to n.
A random walk can end early, for example by leaving a board or reaching a score, and you want the chance of a certain end.
The brute force lists all 8^k paths. That grows too fast, but many paths reach the same square.

The invariant, step by step

dp starts with dp[row][column] = 1.0. The knight is certainly there, and every other square has 0.0.
A step begins with a fresh board nxt filled with 0.0.
For every square (r, c), the code visits each of the 8 moves and computes the target (nr, nc).
If the target is on the board, it adds dp[r][c] / 8 to nxt[nr][nc]. If the target is off the board, it adds nothing.
After all squares are done, dp = nxt. Now dp[r][c] is the probability that the knight is on (r, c) after one more move, having stayed on the board.
This repeats k times. A share that left the board is in no square, so it does not return.
The answer is sum(sum(line) for line in dp), the probability of being on the board after k moves.

Traps

Passing the whole probability. Without / 8, the table counts paths. For n = 3 and k = 2 from (0, 0), the result is 4.0 instead of 0.0625. A probability above 1 is a sign of this mistake.
Updating dp in place. A square passes on a share it has just received, so a knight moves twice in one step. The result is 1.7191162109375 instead of 0.0625 in the same example.
Wrapping around the edge. With (r + dr) % n, a share that should leave the board returns on the other side. No share is ever lost and the result is 1.0. Test 0 <= nr < n instead.
Asking for the wrong total. If the question wants the chance of being on one square, return that square. If it asks for the chance of staying on the board, return the total. Read the question before the last line.
Floating-point error. The values are fractions that need many binary digits. LeetCode accepts a small error, so use float. If an exact answer is required, use fractions.Fraction.

Practice

Canonical LeetCode:Knight Probability in Chessboard (LC 688)New 21 Game (LC 837)Soup Servings (LC 808)

Theory Context•Dynamic Programming

Builds on Grid DP, which you haven’t finished yet.

P2MediumMental model~5 min speedrun

Probability DP (Knight Probability, New 21 Game)

The problem

Knight Probability in Chessboard (LC 688)(opens leetcode.com)

At every move, the knight picks one of its 8 moves with equal chance, even when that move would take it off the board. Once the knight is off the board, it stays off.

Return the probability that the knight is still on the board after it has made k moves.

Example 1

Input:n = 3, k = 2, row = 0, column = 0

Output:0.0625

From the corner, two of the eight moves stay on the board, to (1, 2) and (2, 1). From each of those, two of the eight moves stay on again. So the probability is 2/8 * 2/8 = 0.0625.

Probability DP

state probability dp[s] ➔ spread over the equally likely moves each step ➔ total on the states that count

Spot it when: You want the chance that a random process ends in a certain way: equally likely moves on a board, random draws toward a score, or a walk that can be lost for good.

Probability DP

Python

1	def knight_probability(n: int, k: int, row: int, column: int) -> float:
2	"""Probability DP: spread each square's probability over the 8 knight moves, k times, and total what stays on the board.
3	Time: O(K * N^2) \| Space: O(N^2)
4	"""
5	moves = [(1, 2), (2, 1), (2, -1), (1, -2), (-1, -2), (-2, -1), (-2, 1), (-1, 2)]
6	# dp: dp[r][c] is the probability that the knight stands on (r, c) after the moves made so far, never having left the board
7	dp = [[0.0] * n for _ in range(n)]
8	dp[row][column] = 1.0
9
10	for _ in range(k):
11	nxt = [[0.0] * n for _ in range(n)]
12	for r in range(n):
13	for c in range(n):
14	# 1. Spread Each Square's Probability Over The 8 Moves:
15	# Each move has chance 1/8, so a square passes dp[r][c] / 8 to every target that is still on the board.
16	for dr, dc in moves:
17	nr, nc = r + dr, c + dc
18	if 0 <= nr < n and 0 <= nc < n:
19	nxt[nr][nc] += dp[r][c] / 8
20	# 2. Replace The Board With The New Step:
21	# The share that fell off the board is added nowhere, so it is gone for every later step.
22	dp = nxt
23
24	# 3. Add Up What Is Left On The Board:
25	# Each square holds the probability of being there after k moves without leaving, so their total is the answer.
26	return sum(sum(line) for line in dp)

Invariant: After each step, dp[r][c] is the probability that the knight is on (r, c) after the moves made so far without having left the board.

See it run

Probability DP on a 3 x 3 board, k = 2, step by step

moves 0 of 2on board 1

The top rows are dp, the board before the move. The bottom rows are nxt, the board after it. Each row is a board row r and each column is a board column c.

knight the starting square, with probability 1
from a square that passes its probability on
receive a square in nxt that receives a share

dp[0][0] = 1.0, because the knight is certainly on its starting square. Every other square holds 0.

dp r0

1knight

dp r1

dp r2

nxt r0

nxt r1

nxt r2

1 / 9

Gotchas1 of 3

The trap
Gotcha 1: Passing the whole probability instead of one eighth
Mistake
```
nxt[nr][nc] += dp[r][c]
```
Fix
```
nxt[nr][nc] += dp[r][c] / 8
```
What happens: A knight picks one of its 8 moves with equal chance, so each target receives one eighth of the square's probability. Without the division, each target receives the whole probability. The table then counts paths, and the answer is far above 1.
Example: n = 3, k = 2, row = 0, column = 0
Mistake: returns 4.0Fix: returns 0.0625
Gotcha 2: Updating dp in place instead of building nxt
Mistake
```
dp[nr][nc] += dp[r][c] / 8
```
Fix
```
nxt[nr][nc] += dp[r][c] / 8
```
What happens: One step must read the board before the move and write the board after it. Writing into dp while reading dp lets a square pass on a share it has just received, so the knight moves twice in one step, and the total probability is too large.
Example: n = 3, k = 2, row = 0, column = 0
Mistake: returns 1.7191162109375Fix: returns 0.0625
Gotcha 3: Wrapping a move around the edge of the board
Mistake
```
nr, nc = (r + dr) % n, (c + dc) % n
```
Fix
```
nr, nc = r + dr, c + dc
```
What happens: A move off the board ends the walk: the knight stays off, and its share is lost. Taking % n brings the knight back onto the other side, so no share is ever lost and the answer is always 1.0.
Example: n = 3, k = 2, row = 0, column = 0
Mistake: returns 1.0Fix: returns 0.0625

Not this one if…

You count the number of ways, not a chance, as in Climbing Stairs (LC 70): every way counts as 1 and the counts are added, with no equal-chance weight to carry. See Linear DP
You count the paths from one corner to another on a grid, as in Unique Paths (LC 62): each cell adds the cell above and the cell to the left, and there is no random move to weight. See Grid DP

Deep Dive

The state is a share of probability, not a count

At the start, dp[row][column] = 1.0, because the knight is certainly on the starting square. All other squares hold 0.0. The total over the board is 1.0.

One step spreads each share equally

The knight has 8 moves, and each has the chance 1/8. A square that holds dp[r][c] passes dp[r][c] / 8 to each of its 8 targets. If a target is on the board, nxt[nr][nc] receives that amount.

A target can receive from several squares, so the code uses +=. The result is the sum over all squares that can reach it.

Example: n = 3, start (0, 0). Of the 8 moves, only (1, 2) and (2, 1) stay on the board. So after one step, dp[1][2] = 1/8 and dp[2][1] = 1/8. The other 6/8 are off the board.

A share that leaves the board is lost for good

When a target is off the board, the code adds nothing to nxt. That share is not moved to another square. It is simply missing from the next board, and no later step can bring it back.

A brute force agrees. Of the 64 paths of two moves, exactly 4 stay on the board, and 4 / 64 = 1/16.

Why the table is rebuilt each step

A step reads the board before the move and writes the board after the move. These are two different boards, so the code builds a fresh nxt and then sets dp = nxt.

If the code wrote into dp while it reads dp, a square could pass on a share that it received in the same step. That share would then move twice in one step.

The cost, and the same idea in other problems

60-Second Pitch

Common Questions

Why do you divide by 8, and not count paths?: Each of the 8 moves has the chance 1/8, and the chances of the steps multiply. A square that holds probability p gives p / 8 to each target. If you do not divide, the table counts paths, and the total can be larger than 1. A probability can never be larger than 1.
Why is the lost share not added anywhere?: The question asks for the chance of staying on the board for all k moves. A knight that leaves the board has failed, and it cannot return in a later move. So its share is dropped, and the final total is exactly the chance of success.
What is the time and space complexity of knight_probability?: O(K * N^2) time and O(N^2) space. Each of the K steps visits N^2 squares and tries 8 moves, and 8 is a constant. The space holds dp and nxt, and each has N^2 entries.
How does New 21 Game (LC 837) use the same idea?: The state is the score. dp[i] is the probability of reaching score i, and each draw from 1 to maxPts has the chance 1/maxPts. So dp[i] is the sum of the previous maxPts values below k, divided by maxPts. A running window sum keeps this at O(N) time. The answer is the total of dp[i] for k <= i <= n.
Could you use recursion with memoization instead of a table?: Yes, but it runs in the other direction. A function f(steps_left, r, c) returns the chance of surviving from (r, c) for the rest of the steps, and it averages the 8 targets. The time is the same, O(K * N^2). The table version moves forward and avoids the recursion stack, which is why it is common in interviews.

SWE Reasoning

Spot it

The question asks for a chance, an expected fraction or a probability, not for a count or a best value.
Each step has equally likely random choices, such as the 8 knight moves, a die roll or a random draw.
The next step depends only on the current state, and the state space is small, such as N^2 squares or the scores up to n.
A random walk can end early, for example by leaving a board or reaching a score, and you want the chance of a certain end.
The brute force lists all 8^k paths. That grows too fast, but many paths reach the same square.

The invariant, step by step

dp starts with dp[row][column] = 1.0. The knight is certainly there, and every other square has 0.0.
A step begins with a fresh board nxt filled with 0.0.
For every square (r, c), the code visits each of the 8 moves and computes the target (nr, nc).
If the target is on the board, it adds dp[r][c] / 8 to nxt[nr][nc]. If the target is off the board, it adds nothing.
After all squares are done, dp = nxt. Now dp[r][c] is the probability that the knight is on (r, c) after one more move, having stayed on the board.
This repeats k times. A share that left the board is in no square, so it does not return.
The answer is sum(sum(line) for line in dp), the probability of being on the board after k moves.

Traps

Passing the whole probability. Without / 8, the table counts paths. For n = 3 and k = 2 from (0, 0), the result is 4.0 instead of 0.0625. A probability above 1 is a sign of this mistake.
Updating dp in place. A square passes on a share it has just received, so a knight moves twice in one step. The result is 1.7191162109375 instead of 0.0625 in the same example.
Wrapping around the edge. With (r + dr) % n, a share that should leave the board returns on the other side. No share is ever lost and the result is 1.0. Test 0 <= nr < n instead.
Asking for the wrong total. If the question wants the chance of being on one square, return that square. If it asks for the chance of staying on the board, return the total. Read the question before the last line.
Floating-point error. The values are fractions that need many binary digits. LeetCode accepts a small error, so use float. If an exact answer is required, use fractions.Fraction.

Practice

Canonical LeetCode:Knight Probability in Chessboard (LC 688)New 21 Game (LC 837)Soup Servings (LC 808)