Cherry Pickup (Two Paths Simultaneously)

📋

Problem

Imagine two friends starting at the top-left corner of a grid, each trying to collect as many cherries as possible while moving to the bottom-right corner simultaneously, but they cannot pick the same cherry twice.

Given an n x n grid filled with cherries (represented by 1), empty cells (0), and thorns (-1), two players start at (0,0) and move to (n-1,n-1) simultaneously. Each can only move right or down. They collect cherries on their paths, but if both land on the same cell, the cherry is counted only once. Return the maximum number of cherries both can collect together. If no valid path exists, return 0.

1 ≤ n ≤ 50grid[i][j] ∈ {-1, 0, 1}Both players start at (0,0) and end at (n-1,n-1)Players can only move right or down

Edge cases: Grid with all -1 except start and end → output 0Grid with no cherries → output 0Grid where one path is blocked forcing zero cherries

</>

IDE

def cherryPickup(grid: List[List[int]]) -> int:public int cherryPickup(int[][] grid)int cherryPickup(vector<vector<int>>& grid)function cherryPickup(grid)

def cherryPickup(grid):
    # Write your solution here
    pass

class Solution {
    public int cherryPickup(int[][] grid) {
        // Write your solution here
        return 0;
    }
}

#include <vector>
using namespace std;

int cherryPickup(vector<vector<int>>& grid) {
    // Write your solution here
    return 0;
}

function cherryPickup(grid) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: -1 or negative valuesReturning negative infinity or invalid states instead of 0 when no path exists.✅ Return max(ans, 0) at the end to ensure non-negative output.

Wrong: Overcounted cherries (greater than correct max)Double counting cherries when both players land on the same cell.✅ Add cherries from second player only if positions differ: if (r1 != r2 || c1 != c2).

Wrong: 0 when valid cherries existFailing to explore all valid paths or pruning too aggressively on blocked cells.✅ Ensure DP explores all four possible moves and prunes only invalid states with -1.

Wrong: Timeout / TLEUsing pure recursion without memoization causing exponential time complexity.✅ Implement memoization or bottom-up DP to reduce complexity to O(n^3).

Wrong: Incorrect output on single cell gridNot handling base case n=1 properly.✅ Return grid[0][0] if not blocked, else 0.

✓

Test Cases

Focus on handling minimal and boundary inputs correctly to avoid base case bugs.

Think about common algorithmic pitfalls like greedy traps and double counting.

Optimize your solution to avoid exponential time complexity; use DP memoization or tabulation.

t1_01basic

Input{"grid":[[0,1,-1],[1,0,-1],[1,1,1]]}

Expected5

⏱ Performance - must finish in 2000ms

One optimal path collects cherries at positions (0,1), (1,0), (2,0), (2,1), and (2,2). Both players coordinate to maximize total cherries without double counting.

💡 Think about simulating two players moving simultaneously on the grid.

💡 Use dynamic programming with three parameters to represent both players' positions.

💡 Calculate cherries collected by both players, avoiding double counting when they land on the same cell.

Why it failed: Incorrect output indicates failure to correctly simulate two simultaneous paths or double counting cherries when players overlap. Fix by ensuring dp state tracks both players' positions and cherries are counted once per cell.

✓ Correctly simulates two players moving simultaneously and accumulates cherries without double counting.

t1_02basic

Input{"grid":[[1,1,1],[1,-1,1],[1,1,1]]}

Expected7

⏱ Performance - must finish in 2000ms

Optimal paths collect cherries from most cells except the blocked cell (1,1). Total cherries collected is 7.

💡 Consider how blocked cells (-1) affect possible paths for both players.

💡 Use memoization or bottom-up DP to avoid recomputing states and handle obstacles.

💡 Ensure to handle cases where one path is forced to detour due to blocked cells.

Why it failed: Wrong output likely due to ignoring blocked cells or failing to handle path constraints properly. Fix by pruning invalid states where either player steps on -1.

✓ Correctly accounts for blocked cells and finds maximum cherries collectible.

t2_01edge

Input{"grid":[[0]]}

Expected0

⏱ Performance - must finish in 2000ms

Single cell grid with no cherries; maximum cherries collected is 0.

💡 Check behavior when grid size is minimum (n=1).

💡 Ensure code handles single cell without errors.

💡 Return the cell value if it's not blocked, else 0.

Why it failed: Fails on single element grid due to incorrect base case handling. Fix by returning grid[0][0] if not blocked.

✓ Handles single cell grid correctly.

t2_02edge

Input{"grid":[[0,0],[0,0]]}

Expected0

⏱ Performance - must finish in 2000ms

Grid with no cherries; maximum cherries collected is 0.

💡 Test grids with no cherries to verify no false positives.

💡 DP should return 0 if no cherries are present.

💡 Ensure no negative values are returned when no cherries exist.

Why it failed: Incorrect output due to assuming cherries exist; fix by initializing dp with 0 and returning max with 0.

✓ Correctly returns 0 when no cherries are present.

t2_03edge

Input{"grid":[[0,-1],[1,0]]}

Expected0

⏱ Performance - must finish in 2000ms

One path blocked by thorn (-1) forcing no valid path; result is 0.

💡 Check how blocked cells prevent any valid path.

💡 DP states leading to blocked cells should be invalidated.

💡 Return 0 if no valid path exists.

Why it failed: Fails to detect blocked paths and returns non-zero. Fix by pruning states with -1 cells.

✓ Correctly returns 0 when no valid path exists.

t3_01corner

Input{"grid":[[1,0,0],[0,1,0],[0,0,1]]}

Expected3

⏱ Performance - must finish in 2000ms

Cherries only on diagonal; both players must pick cherries on diagonal cells without overlap counting twice.

💡 Test if solution correctly handles cherries only on diagonal cells.

💡 Check if double counting occurs when both players land on same diagonal cell.

💡 Fix by adding cherries only once when players share the same cell.

Why it failed: Double counting cherries on overlapping cells causes output > 3. Fix by adding cherries only once if players share cell.

✓ Correctly counts cherries once per cell even if both players land there.

t3_02corner

Input{"grid":[[1,1,1,1],[1,-1,-1,1],[1,-1,-1,1],[1,1,1,1]]}

Expected10

⏱ Performance - must finish in 2000ms

Grid with blocked cells forcing detours; greedy approach picking local max cherries fails here.

💡 Beware of greedy approaches that pick immediate cherries without considering future blocks.

💡 Use DP to explore all valid paths and maximize total cherries.

💡 Memoize states to avoid recomputation and handle blocked cells correctly.

Why it failed: Greedy approach fails by choosing blocked paths or suboptimal routes. Fix by implementing DP with memoization over both players' positions.

✓ DP correctly finds maximum cherries despite blocked cells.

t3_03corner

Input{"grid":[[1,1,1],[1,1,1],[1,1,1]]}

Expected9

⏱ Performance - must finish in 2000ms

Tests confusion between 0/1 and unbounded knapsack style counting; cherries can only be picked once per cell.

💡 Ensure cherries are counted once per cell, not multiple times.

💡 DP state must track positions of both players simultaneously.

💡 Avoid summing cherries multiple times by careful state transitions.

Why it failed: Counting cherries multiple times per cell inflates result. Fix by counting cherries once per cell per step.

✓ Correctly counts cherries once per cell for both players.

t4_01performance

Input{"grid":[[0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1],[1,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0],[0,1,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0],[0,0,1,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1],[1,0,0,1,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0],[0,1,0,0,1,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0],[0,0,1,0,0,1,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1],[1,0,0,1,0,0,1,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0],[0,1,0,0,1,0,0,1,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0],[0,0,1,0,0,1,0,0,1,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1],[1,0,0,1,0,0,1,0,0,1,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0],[0,1,0,0,1,0,0,1,0,0,1,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0],[0,0,1,0,0,1,0,0,1,0,0,1,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1],[1,0,0,1,0,0,1,0,0,1,0,0,1,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0],[0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0],[0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1],[1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0],[0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0],[0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1],[1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0],[0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0],[0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1],[1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0],[0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0],[0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1],[1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0],[0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0],[0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1],[1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0],[0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0],[0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1],[1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0],[0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0],[0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1],[1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0],[0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0],[0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,1,0,0,1,0,0,1,0,0,1,0,0,1],[1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,1,0,0,1,0,0,1,0,0,1,0,0],[0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,1,0,0,1,0,0,1,0,0,1,0],[0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,1,0,0,1,0,0,1,0,0,1],[1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,1,0,0,1,0,0,1,0,0],[0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,1,0,0,1,0,0,1,0],[0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,1,0,0,1,0,0,1],[1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,1,0,0,1,0,0],[0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,1,0,0,1,0],[0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,1,0,0,1],[1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,1,0,0],[0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,1,0],[0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,1],[1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0]]}

Expectednull

⏱ Performance - must finish in 2000ms

Large grid with n=50; O(n^3) DP must complete within 2 seconds.

💡 DP solution has O(n^3) complexity; brute force is exponential and will TLE.

💡 Use memoization or bottom-up DP to optimize overlapping subproblems.

💡 Avoid recomputing states by caching results for pairs of positions.

Why it failed: TLE occurs due to exponential brute force recursion. Fix by implementing DP with memoization or bottom-up tabulation to achieve O(n^3) time.

✓ Efficient DP solution runs within time limits confirming O(n^3) complexity.

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. What is the time complexity of the bottom-up dynamic programming solution for the Stone Game problem with n piles, and why?

medium

A. O(n^3) because of three nested loops over the piles

B. O(n^2) because the DP table of size nxn is filled once with constant work per cell

C. O(2^n) because all subsets of piles are considered

D. O(n) because only linear passes over the piles are needed

Solution

1. Step 1: Identify loops in bottom-up DP

   There are two nested loops: one for length from 2 to n, and one for start index i, total O(n^2) iterations.

2. Step 2: Constant work per dp[i][j]

   Each dp[i][j] is computed with a constant number of operations (max of two values), so total time is O(n^2).

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   DP table size nxn filled once with O(1) work per cell [OK]

Hint: Two nested loops over intervals -> O(n^2) [OK]

Common Mistakes:

• Confusing recursion stack space with time
• Assuming triple nested loops cause O(n^3)

3. The following code attempts to solve the Strange Printer problem using bottom-up DP. Which line contains a subtle bug that can cause incorrect results on inputs like "aba"?

medium

A. Line 18: dp[i][j] = dp[i][j - 1] + 1 assignment

B. Line 13: dp[i][i] = 1 initialization

C. Line 4: compressed.append(c) without checking for duplicates

D. Line 21: if s[k] == s[j] condition

Solution

1. Step 1: Identify compression step

   Line 4 appends every character without checking if it equals the last compressed character, so no compression occurs.

2. Step 2: Understand impact of missing compression

   Without compression, the DP runs on the full string length, causing inefficiency and possibly incorrect merges, especially on inputs like "aba" where compression reduces complexity.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Compression step must skip duplicates to optimize DP [OK]

Hint: Compression must skip consecutive duplicates to avoid TLE and errors [OK]

Common Mistakes:

• Forgetting to compress string before DP

4. Suppose the problem is modified so that you can reuse the same color for adjacent houses, but you want to minimize the total cost. Which modification to the DP solution is correct?

hard

A. Use brute force recursion without memoization since constraints are relaxed.

B. Keep excluding the previous color but add a penalty cost for same color adjacency.

C. Remove the condition excluding the previous color when computing min_prev; just take min(dp) for all colors.

D. Use a greedy approach picking the cheapest color for each house independently.

Solution

1. Step 1: Understand constraint relaxation

   Allowing same color for adjacent houses removes the need to exclude previous color in DP transitions.

2. Step 2: Modify DP accordingly

   Now min_prev is simply min(dp) over all colors, no exclusion needed. This simplifies the DP and still finds minimum cost.

3. Step 3: Evaluate other options

   Adding penalty is unnecessary. Brute force is inefficient. Greedy fails because costs vary per house and color.

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   Relaxed constraints allow including all colors in min calculation [OK]

Hint: Relaxed constraints mean no exclusion of previous color in DP [OK]

Common Mistakes:

• Still excluding previous color unnecessarily
• Adding penalty complicates solution
• Using brute force or greedy incorrectly

5. Suppose the triangle can contain negative numbers and you want to find the minimum path sum. Which modification to the bottom-up DP approach is necessary to correctly handle this variant?

hard

A. Add a check to reset dp values to zero if they become negative during updates

B. Use top-down DP with memoization to avoid incorrect overwrites caused by negative values

C. No modification needed; the existing bottom-up DP works for negative numbers as well

D. Use a breadth-first search to find the minimum path sum instead of DP

Solution

1. Step 1: Understand DP correctness with negative numbers

   Bottom-up DP computes minimum sums by combining current value with min of two below; negative values do not break this logic.

2. Step 2: Confirm no overwrite or invalid assumptions

   DP updates are independent of sign; no reset or BFS needed.

3. Step 3: Conclude no modification needed

   The existing bottom-up DP approach correctly handles negative numbers without changes.

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   DP min operations handle negatives naturally [OK]

Hint: DP min works regardless of sign [OK]

Common Mistakes:

• Assuming negative numbers require resetting dp
• Thinking BFS is needed for negative weights
• Believing top-down memoization fixes negative value issues