Cherry Pickup (Two Paths Simultaneously)

▶

Steps

setup

Initialize DP array with -inf

Create a 3D dp array of size n x n x n filled with -inf to represent impossible states initially.

💡 Initializing with -inf ensures only reachable states will be updated later, preventing invalid paths from influencing results.

Line:

dp = [[[-float('inf')] * n for _ in range(n)] for __ in range(n)]

💡 All states start as unreachable except the base case to be set next.

setup

Set base case dp[0][0][0]

Set dp[0][0][0] to grid[0][0] (0) as both players start at the top-left corner.

💡 This base case anchors the DP, representing the starting point with collected cherries equal to the grid cell value.

Line:

dp[0][0][0] = grid[0][0]

💡 The starting position is reachable with initial cherries collected.

fill_cells

Step 1: Iterate over r1 and r2 to fill dp for step=1

For step=1, consider all valid r1 and r2 positions and compute c1 and c2. Skip invalid or blocked cells.

💡 At each step, players move one cell right or down; this step explores all possible positions after the first move.

Line:

for r1 in range(max(0, step-(n-1)), min(n, step+1)):
  c1 = step - r1
  for r2 in range(max(0, step-(n-1)), min(n, step+1)):
    c2 = step - r2

💡 Positions are constrained by the step number and grid size; invalid positions are ignored.

fill_cells

Step 1: Update dp for r1=0, c1=1 and r2=0, c2=1

Calculate dp[0][1][0] by checking previous states and adding cherries at (0,1) and (0,1). Avoid double counting since positions are the same.

💡 When both players land on the same cell, count cherries only once to avoid overcounting.

Line:

if grid[r1][c1] != -1 and grid[r2][c2] != -1:
  candidates.append(dp[r1][c1-1][r2])
max_prev = max(candidates)
val = max_prev + grid[r1][c1]
if r1 != r2 or c1 != c2:
  val += grid[r2][c2]
dp[r1][c1][r2] = max(dp[r1][c1][r2], val)

💡 The dp value updates by adding cherries at the new positions, respecting overlap.

fill_cells

Step 1: Update dp for r1=1, c1=0 and r2=1, c2=0

Calculate dp[1][0][1] by checking previous states and adding cherries at (1,0) and (1,0). Avoid double counting since positions are the same.

💡 Similar to previous step, handle overlapping positions carefully.

Line:

if grid[r1][c1] != -1 and grid[r2][c2] != -1:
  candidates.append(dp[r1-1][c1][r2-1])
max_prev = max(candidates)
val = max_prev + grid[r1][c1]
if r1 != r2 or c1 != c2:
  val += grid[r2][c2]
dp[r1][c1][r2] = max(dp[r1][c1][r2], val)

💡 The dp value updates by adding cherries at the new positions, respecting overlap.

fill_cells

Step 2: Iterate over r1 and r2 for step=2

For step=2, compute all valid (r1, c1) and (r2, c2) positions and prepare to update dp accordingly.

💡 Step 2 corresponds to players moving further down or right; all reachable positions are considered.

Line:

for r1 in range(max(0, step-(n-1)), min(n, step+1)):
  c1 = step - r1
  for r2 in range(max(0, step-(n-1)), min(n, step+1)):
    c2 = step - r2

💡 Positions are constrained by grid size and step number.

fill_cells

Step 2: Update dp for r1=1, c1=1 and r2=1, c2=1

Calculate dp[1][1][1] by checking all valid previous states and adding cherries at (1,1) and (1,1), avoiding double counting.

💡 Players meet at the same cell; count cherries once.

Line:

candidates = []
if r1 > 0 and r2 > 0:
  candidates.append(dp[r1-1][c1][r2-1])
if r1 > 0 and c2 > 0:
  candidates.append(dp[r1-1][c1][r2])
if c1 > 0 and r2 > 0:
  candidates.append(dp[r1][c1-1][r2-1])
if c1 > 0 and c2 > 0:
  candidates.append(dp[r1][c1-1][r2])
max_prev = max(candidates)
val = max_prev + grid[r1][c1]
if r1 != r2 or c1 != c2:
  val += grid[r2][c2]
dp[r1][c1][r2] = max(dp[r1][c1][r2], val)

💡 The dp value accumulates cherries from previous best states plus current cell cherries.

fill_cells

Step 2: Update dp for r1=2, c1=0 and r2=2, c2=0

Calculate dp[2][0][2] by checking previous states and adding cherries at (2,0) and (2,0), avoiding double counting.

💡 Players meet at the same cell; count cherries once.

Line:

candidates = []
if r1 > 0 and r2 > 0:
  candidates.append(dp[r1-1][c1][r2-1])
if r1 > 0 and c2 > 0:
  candidates.append(dp[r1-1][c1][r2])
if c1 > 0 and r2 > 0:
  candidates.append(dp[r1][c1-1][r2-1])
if c1 > 0 and c2 > 0:
  candidates.append(dp[r1][c1-1][r2])
max_prev = max(candidates)
val = max_prev + grid[r1][c1]
if r1 != r2 or c1 != c2:
  val += grid[r2][c2]
dp[r1][c1][r2] = max(dp[r1][c1][r2], val)

💡 The dp value accumulates cherries from previous best states plus current cell cherries.

fill_cells

Step 3: Iterate over r1 and r2 for step=3

For step=3, compute all valid (r1, c1) and (r2, c2) positions and prepare to update dp accordingly.

💡 Step 3 corresponds to players moving further; all reachable positions are considered.

Line:

for r1 in range(max(0, step-(n-1)), min(n, step+1)):
  c1 = step - r1
  for r2 in range(max(0, step-(n-1)), min(n, step+1)):
    c2 = step - r2

💡 Positions are constrained by grid size and step number.

fill_cells

Step 3: Update dp for r1=2, c1=1 and r2=2, c2=1

Calculate dp[2][1][2] by checking previous states and adding cherries at (2,1) and (2,1), avoiding double counting.

💡 Players meet at the same cell; count cherries once.

Line:

candidates = []
if r1 > 0 and r2 > 0:
  candidates.append(dp[r1-1][c1][r2-1])
if r1 > 0 and c2 > 0:
  candidates.append(dp[r1-1][c1][r2])
if c1 > 0 and r2 > 0:
  candidates.append(dp[r1][c1-1][r2-1])
if c1 > 0 and c2 > 0:
  candidates.append(dp[r1][c1-1][r2])
max_prev = max(candidates)
val = max_prev + grid[r1][c1]
if r1 != r2 or c1 != c2:
  val += grid[r2][c2]
dp[r1][c1][r2] = max(dp[r1][c1][r2], val)

💡 The dp value accumulates cherries from previous best states plus current cell cherries.

fill_cells

Step 4: Iterate over r1 and r2 for step=4

For step=4, compute all valid (r1, c1) and (r2, c2) positions and prepare to update dp accordingly.

💡 Step 4 is the final step where both players reach bottom-right corner.

Line:

for r1 in range(max(0, step-(n-1)), min(n, step+1)):
  c1 = step - r1
  for r2 in range(max(0, step-(n-1)), min(n, step+1)):
    c2 = step - r2

💡 Positions are constrained by grid size and step number.

fill_cells

Step 4: Update dp for r1=2, c1=2 and r2=2, c2=2

Calculate dp[2][2][2] by checking previous states and adding cherries at (2,2) and (2,2), avoiding double counting.

💡 Players meet at the same cell; count cherries once.

Line:

candidates = []
if r1 > 0 and r2 > 0:
  candidates.append(dp[r1-1][c1][r2-1])
if r1 > 0 and c2 > 0:
  candidates.append(dp[r1-1][c1][r2])
if c1 > 0 and r2 > 0:
  candidates.append(dp[r1][c1-1][r2-1])
if c1 > 0 and c2 > 0:
  candidates.append(dp[r1][c1-1][r2])
max_prev = max(candidates)
val = max_prev + grid[r1][c1]
if r1 != r2 or c1 != c2:
  val += grid[r2][c2]
dp[r1][c1][r2] = max(dp[r1][c1][r2], val)

💡 The dp value accumulates cherries from previous best states plus current cell cherries.

reconstruct

Final Step: Return the maximum cherries collected

Return the maximum cherries collected when both players reach the bottom-right corner, or 0 if unreachable.

💡 The answer is the value in dp[n-1][n-1][n-1], representing both players at the destination.

Line:

return max(dp[n-1][n-1][n-1], 0)

💡 The DP table has captured the maximum cherries collectible by two coordinated paths.

from typing import List

def cherryPickup(grid: List[List[int]]) -> int:
    n = len(grid)  # STEP 1
    dp = [[[-float('inf')] * n for _ in range(n)] for __ in range(n)]  # STEP 1
    dp[0][0][0] = grid[0][0]  # STEP 2
    for step in range(1, 2 * (n - 1) + 1):  # STEP 3
        for r1 in range(max(0, step - (n - 1)), min(n, step + 1)):  # STEP 3
            c1 = step - r1  # STEP 3
            if c1 < 0 or c1 >= n:
                continue
            for r2 in range(max(0, step - (n - 1)), min(n, step + 1)):  # STEP 3
                c2 = step - r2  # STEP 3
                if c2 < 0 or c2 >= n:
                    continue
                if grid[r1][c1] == -1 or grid[r2][c2] == -1:  # STEP 4
                    continue
                candidates = []  # STEP 5
                if r1 > 0 and r2 > 0:
                    candidates.append(dp[r1 - 1][c1][r2 - 1])
                if r1 > 0 and c2 > 0:
                    candidates.append(dp[r1 - 1][c1][r2])
                if c1 > 0 and r2 > 0:
                    candidates.append(dp[r1][c1 - 1][r2 - 1])
                if c1 > 0 and c2 > 0:
                    candidates.append(dp[r1][c1 - 1][r2])
                max_prev = max(candidates) if candidates else -float('inf')  # STEP 5
                if max_prev == -float('inf'):
                    continue
                val = max_prev + grid[r1][c1]  # STEP 5
                if r1 != r2 or c1 != c2:
                    val += grid[r2][c2]  # STEP 5
                dp[r1][c1][r2] = max(dp[r1][c1][r2], val)  # STEP 5
    return max(dp[n - 1][n - 1][n - 1], 0)  # STEP 6

📊

Cherry Pickup (Two Paths Simultaneously) - Watch the Algorithm Execute, Step by Step

Watching each update to the DP table reveals how the algorithm considers all possible previous states and coordinates two paths to maximize cherry collection.

Item 0 - wt:0 val:0

i\w	0	1	2
i=0	-∞	-∞	-∞
i=1	-∞	-∞	-∞
i=2	-∞	-∞	-∞

-inf (unreachable)

Item 0 - wt:0 val:0

i\w	0	1	2
i=0	0	-∞	-∞
i=1	-∞	-∞	-∞
i=2	-∞	-∞	-∞

start dp[0][0][0] = 0

Item 0 - wt:0 val:0

i\w	0	1	2
i=0	-∞	-∞	-∞
i=1	-∞	-∞	-∞
i=2	-∞	-∞	-∞

r1=0,c1=1

Item 0 - wt:1 val:1

i\w	0	1	2
i=0	-∞	1	-∞
i=1	-∞	-∞	-∞
i=2	-∞	-∞	-∞

prev dp[0][0][0]=0

Item 1 - wt:1 val:1

i\w	0	1	2
i=0	-∞	1	-∞
i=1	1	-∞	-∞
i=2	-∞	-∞	-∞

prev dp[0][0][0]=0

Item 0 - wt:0 val:0

i\w	0	1	2
i=0	-∞	1	-∞
i=1	1	-∞	-∞
i=2	-∞	-∞	-∞

r1=0,c1=2

Item 1 - wt:1 val:2

i\w	0	1	2
i=0	-∞	1	-∞
i=1	1	2	-∞
i=2	-∞	-∞	-∞

prev dp[0][1][0]=1

Item 2 - wt:1 val:3

i\w	0	1	2
i=0	-∞	1	-∞
i=1	1	2	-∞
i=2	3	-∞	-∞

prev dp[1][1][1]=2

Item 0 - wt:0 val:0

i\w	0	1	2
i=0	-∞	1	-∞
i=1	1	2	-∞
i=2	3	4	-∞

r1=1,c1=2

Item 2 - wt:1 val:4

i\w	0	1	2
i=0	-∞	1	-∞
i=1	1	2	-∞
i=2	3	4	-∞

prev dp[2][0][2]=3

Item 0 - wt:0 val:0

i\w	0	1	2
i=0	-∞	1	-∞
i=1	1	2	-∞
i=2	3	4	-∞

r1=2,c1=2

Item 2 - wt:1 val:5

i\w	0	1	2
i=0	-∞	1	-∞
i=1	1	2	-∞
i=2	3	4	5

prev dp[2][1][2]=4

Item 2 - wt:1 val:5

i\w	0	1	2
i=0	-∞	1	-∞
i=1	1	2	-∞
i=2	3	4	5

answer dp[2][2][2] = 5

Key Takeaways

✓ The DP table tracks two players' positions simultaneously, enabling coordination to maximize cherry collection.

This simultaneous tracking is hard to grasp from code alone but becomes clear when seeing the DP table update.

✓ Each dp cell depends on up to four previous states, reflecting all possible moves of both players at the previous step.

Visualizing these dependencies clarifies the fill order and why the algorithm considers multiple previous states.

✓ When both players land on the same cell, cherries are counted only once to avoid double counting.

This subtle condition is easier to understand when watching the step-by-step updates and the effect on dp values.

Practice

1. What is the time complexity of the space-optimized bottom-up DP solution for the Maximal Square problem on an m x n matrix, and why might some candidates incorrectly think it is higher?

medium

A. O(m^3) because checking all squares requires nested loops

B. O(m * n * min(m,n)) because of checking all possible square sizes

C. O(m * n) because each cell is processed once with constant time updates

D. O(m + n) because only rows and columns are iterated separately

Solution

1. Step 1: Identify loops in the code

   Two nested loops iterate over rows and columns, each cell processed once.

2. Step 2: Understand DP update cost

   Each dp update is O(1), no nested checks for squares inside loops.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   DP avoids checking all squares explicitly [OK]

Hint: DP processes each cell once with constant work [OK]

Common Mistakes:

• Confusing brute force with DP complexity
• Assuming nested loops check all squares
• Ignoring constant time DP updates

2. The following code attempts to implement the space-optimized DP solution for Maximal Square. Identify the line containing the subtle bug that causes incorrect results on some inputs.

def maximalSquare(matrix):
    if not matrix or not matrix[0]:
        return 0
    rows, cols = len(matrix), len(matrix[0])
    dp = [0] * (cols + 1)
    max_side = 0
    prev = 0
    for i in range(rows):
        for j in range(1, cols + 1):
            temp = dp[j]
            if matrix[i][j-1] == '1':
                dp[j] = 1 + min(dp[j], dp[j-1], prev)  # Bug here
                max_side = max(max_side, dp[j])
            else:
                dp[j] = 0
            prev = temp
    return max_side * max_side

medium

A. Line with 'dp[j] = 1 + min(dp[j], dp[j-1], dp[j-1])'

B. Line with 'temp = dp[j]'

C. Line with 'prev = temp'

D. Line with 'max_side = max(max_side, dp[j])'

Solution

1. Step 1: Identify the DP recurrence

   The recurrence requires min(dp[j], dp[j-1], prev), but code uses dp[j-1] twice, missing 'prev'.

2. Step 2: Understand impact

   Using dp[j-1] twice ignores the diagonal value 'prev', causing incorrect dp values and max square size.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Correct recurrence uses three distinct values [OK]

Hint: Check if all three DP states are used in min() [OK]

Common Mistakes:

• Forgetting to use 'prev' in min()
• Overwriting dp before using dependencies
• Incorrect dp initialization

3. The following code attempts to solve the Stone Game problem using bottom-up DP. Identify the line containing the subtle bug that causes incorrect results on some inputs.

def stoneGame(piles):
    n = len(piles)
    dp = [[0]*n for _ in range(n)]
    for i in range(n):
        dp[i][i] = piles[i]
    for length in range(2, n+1):
        for i in range(n - length + 1):
            j = i + length - 1
            dp[i][j] = max(piles[i] + dp[i+1][j], piles[j] + dp[i][j-1])
    return dp[0][n-1] > 0

medium

A. Line computing dp[i][j] = max(piles[i] + dp[i+1][j], piles[j] + dp[i][j-1])

B. Line initializing dp[i][i] = piles[i]

C. Line defining the outer loop for length in range(2, n+1)

D. Line returning dp[0][n-1] > 0

Solution

1. Step 1: Understand dp state meaning

   dp[i][j] should represent the maximum difference in stones the current player can achieve over the opponent.

2. Step 2: Identify incorrect recurrence

   The buggy line adds piles[i] + dp[i+1][j], which ignores the opponent's optimal response. The correct formula subtracts dp[i+1][j] to account for opponent's best play.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Correct recurrence uses subtraction, not addition [OK]

Hint: DP recurrence must subtract opponent's score [OK]

Common Mistakes:

• Adding dp values instead of subtracting opponent's score
• Forgetting base case initialization

4. What is the time complexity of the space-optimized bottom-up dynamic programming solution for the Unique Paths problem on an m x n grid?

medium

A. O(m^2 * n^2)

B. O(m + n)

C. O(m * n * min(m, n))

D. O(m * n)

Solution

1. Step 1: Identify loops in the code

   The solution uses two nested loops: outer loop runs m-1 times, inner loop runs n-1 times.

2. Step 2: Calculate total operations

   Total operations ≈ (m-1) * (n-1) -> O(m * n). No extra hidden loops or recursion stack.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Nested loops over m and n -> O(m*n) [OK]

Hint: Nested loops over m and n -> O(m*n) [OK]

Common Mistakes:

• Confusing with recursion exponential time
• Forgetting loops multiply complexity

5. Suppose the problem changes so that you can move down to the same column or adjacent columns multiple times, but you want to find the minimum falling path sum where you can reuse rows multiple times (i.e., you can revisit rows). Which modification to the bottom-up DP approach correctly handles this variant?

hard

A. Use the original DP but memoize results to avoid recomputation

B. Use the same bottom-up DP but allow cycles by iterating until no dp changes occur

C. Switch to a shortest path algorithm like Bellman-Ford on a graph representing allowed moves

D. Apply greedy approach picking minimum adjacent values repeatedly

Solution

1. Step 1: Understand the variant with row reuse

   Allowing revisiting rows means cycles in the path graph, which breaks the acyclic assumption of DP.

2. Step 2: Identify suitable algorithm

   Model the problem as a graph with edges representing allowed moves and use Bellman-Ford to find shortest paths with possible cycles.

3. Step 3: Why other options fail

   Bottom-up DP assumes acyclic progression; greedy ignores global optimality; memoization doesn't handle cycles properly.

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   Bellman-Ford handles negative cycles and repeated nodes [OK]

Hint: Cycles require graph shortest path algorithms, not DP [OK]

Common Mistakes:

• Trying to reuse DP without cycle handling
• Assuming memoization solves cycles