Cheapest Flights Within K Stops

▶

Steps

setup

Initialize cost arrays

Initialize the 'prev' cost array with infinity for all cities except the source city 0, which is set to 0. This represents the cost to reach each city with 0 stops.

💡 Setting the source cost to zero establishes the base case for DP; all other cities are initially unreachable.

Line:

INF = float('inf')
prev = [INF] * n
prev[src] = 0

💡 The algorithm starts with known cost 0 at source and unknown costs elsewhere.

expand

Start iteration 1 (up to 1 stop)

Begin the first iteration where we allow up to 1 stop. Copy 'prev' to 'curr' to start relaxing edges based on previous costs.

💡 Copying prev to curr preserves previous iteration costs before relaxation updates.

Line:

for _ in range(K + 1):
    curr = prev[:]

💡 We prepare a fresh cost array for this iteration to update with relaxed edges.

relax

Relax edge 0 -> 1

Check if city 0 is reachable (cost != ∞). Since prev[0] = 0, update curr[1] to min(curr[1], prev[0] + 100) = 100.

💡 Relaxing edges updates costs to reach neighbors if a cheaper path is found.

Line:

for u, v, w in flights:
    if prev[u] != INF:
        curr[v] = min(curr[v], prev[u] + w)

💡 Relaxation propagates known costs to neighbors, improving cost estimates.

relax

Relax edge 1 -> 2

Check if city 1 is reachable in prev. prev[1] is ∞, so no update to curr[2] is made from this edge.

💡 Only edges from reachable cities can relax costs to neighbors.

Line:

if prev[u] != INF:
    curr[v] = min(curr[v], prev[u] + w)

💡 Relaxation depends on previous iteration's reachable nodes.

relax

Relax edge 0 -> 2

Check if city 0 is reachable. prev[0] = 0, so update curr[2] to min(curr[2], prev[0] + 500) = 500.

💡 Relaxing direct flights from source updates costs even if longer than other paths.

Line:

if prev[u] != INF:
    curr[v] = min(curr[v], prev[u] + w)

💡 Direct flights provide initial cost estimates for destination city.

shrink

Finish iteration 1 and swap arrays

Finish relaxing all edges for iteration 1. Swap prev and curr so prev now holds updated costs for next iteration.

💡 Swapping arrays prepares for next iteration with updated costs.

Line:

prev = curr

💡 The DP state advances by one stop allowed, with updated minimum costs.

expand

Start iteration 2 (up to 2 stops)

Begin second iteration allowing up to 2 stops. Copy prev to curr to prepare for edge relaxations.

💡 Each iteration allows one more stop, expanding reachable paths.

Line:

for _ in range(K + 1):
    curr = prev[:]

💡 We prepare to find cheaper paths with one additional stop allowed.

relax

Relax edge 0 -> 1 again

Check if city 0 is reachable in prev (cost 0). Update curr[1] to min(curr[1], prev[0] + 100) = min(100, 0+100) = 100 (no change).

💡 Relaxation may not always improve costs but confirms current best.

Line:

if prev[u] != INF:
    curr[v] = min(curr[v], prev[u] + w)

💡 Relaxation maintains or improves costs, never worsens.

relax

Relax edge 1 -> 2 to improve cost

City 1 is reachable with cost 100 in prev. Update curr[2] to min(curr[2], prev[1] + 100) = min(500, 100 + 100) = 200.

💡 This relaxation finds a cheaper path to city 2 via city 1.

Line:

if prev[u] != INF:
    curr[v] = min(curr[v], prev[u] + w)

💡 Relaxation can improve costs by considering intermediate stops.

relax

Relax edge 0 -> 2 again

City 0 is reachable with cost 0. Update curr[2] to min(curr[2], prev[0] + 500) = min(200, 0 + 500) = 200 (no change).

💡 Relaxation confirms the cheaper path found via city 1 remains best.

Line:

if prev[u] != INF:
    curr[v] = min(curr[v], prev[u] + w)

💡 The algorithm keeps the minimum cost found so far.

shrink

Finish iteration 2 and swap arrays

Finish relaxing all edges for iteration 2. Swap prev and curr so prev now holds the final updated costs.

💡 Swapping arrays finalizes costs after allowing up to K stops.

Line:

prev = curr

💡 The DP arrays now contain the minimum costs with up to K stops.

reconstruct

Return final answer

Return the cost to reach destination city 2 from prev array. Since prev[2] = 200, return 200 as the cheapest price within K stops.

💡 The final DP array holds the answer after all relaxations.

Line:

return prev[dst] if prev[dst] != INF else -1

💡 The DP approach successfully finds the minimum cost path with constraints.

def findCheapestPrice(n, flights, src, dst, K):
    INF = float('inf')
    prev = [INF] * n  # STEP 1
    prev[src] = 0    # STEP 1
    for _ in range(K + 1):  # STEP 2
        curr = prev[:]      # STEP 2
        for u, v, w in flights:  # STEP 3-5,8-10
            if prev[u] != INF:
                curr[v] = min(curr[v], prev[u] + w)
        prev = curr          # STEP 6,11
    return prev[dst] if prev[dst] != INF else -1  # STEP 12

if __name__ == '__main__':
    n = 3
    flights = [[0,1,100],[1,2,100],[0,2,500]]
    src = 0
    dst = 2
    K = 1
    print(findCheapestPrice(n, flights, src, dst, K))  # Output: 200

📊

Cheapest Flights Within K Stops - Watch the Algorithm Execute, Step by Step

Watching each relaxation and update helps you understand how dynamic programming propagates minimum costs through the graph over iterations.

Visiting: none

0

1

2

Visiting: none

0

1

2

Visiting: 0

Edge: 0 → 1

0

1

2

Visiting: 1

Edge: 1 → 2

0

1

2

Visiting: 0

Edge: 0 → 2

0

1

2

Visiting: none

0

1

2

Visiting: none

0

1

2

Visiting: 0

Edge: 0 → 1

0

1

2

Visiting: 1

Edge: 1 → 2

0

1

2

Visiting: 0

Edge: 0 → 2

0

1

2

Visiting: none

0

1

2

Visiting: 2

0

1

2

Key Takeaways

✓ Dynamic programming propagates minimum costs through the graph by iteratively relaxing edges up to K+1 times.

This iterative relaxation is hard to visualize from code alone but becomes clear when watching each edge update step.

✓ The algorithm maintains two arrays to avoid using updated values within the same iteration, ensuring correctness.

Seeing the copy and swap of arrays clarifies why we don't update costs in place during relaxation.

✓ Relaxation only updates costs if the source city is reachable in the previous iteration, preventing invalid paths.

This conditional check is subtle in code but critical to understand how unreachable nodes don't affect costs.

Practice

1. Consider the following Python code implementing the Cherry Pickup problem using bottom-up DP. Given the input grid below, what is the final returned value?

grid = [
  [0, 1, -1],
  [1, 0, -1],
  [1, 1,  1]
]

from typing import List

def cherryPickup(grid: List[List[int]]) -> int:
    n = len(grid)
    dp = [[[-float('inf')] * n for _ in range(n)] for __ in range(n)]
    dp[0][0][0] = grid[0][0]
    for step in range(1, 2 * (n - 1) + 1):
        for r1 in range(max(0, step - (n - 1)), min(n, step + 1)):
            c1 = step - r1
            if c1 < 0 or c1 >= n:
                continue
            for r2 in range(max(0, step - (n - 1)), min(n, step + 1)):
                c2 = step - r2
                if c2 < 0 or c2 >= n:
                    continue
                if grid[r1][c1] == -1 or grid[r2][c2] == -1:
                    continue
                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])
                best_prev = max(candidates) if candidates else -float('inf')
                if best_prev == -float('inf'):
                    continue
                val = best_prev + grid[r1][c1]
                if r1 != r2:
                    val += grid[r2][c2]
                dp[r1][c1][r2] = max(dp[r1][c1][r2], val)
    return max(0, dp[n - 1][n - 1][n - 1])

print(cherryPickup(grid))

easy

A. 6

B. 5

C. 4

D. 3

Solution

1. Step 1: Trace dp states for step=4 (final step for 3x3 grid)

   At step=4, both players reach bottom-right (2,2). The dp value dp[2][2][2] accumulates max cherries collected along valid paths avoiding thorns (-1).

2. Step 2: Calculate max cherries collected

   By tracing paths, max cherries collected is 6, considering both players' paths and avoiding double counting.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Manual path tracing confirms max cherries = 6 [OK]

Hint: Trace dp at final step for both players [OK]

Common Mistakes:

• Off-by-one errors in step or indices
• Double counting cherries when players overlap
• Ignoring thorn cells leading to invalid paths

2. You are given a 2D grid representing a dungeon where each cell contains an integer indicating health points gained or lost upon entering. You start at the top-left and must reach the bottom-right cell, moving only right or down. Your health must never drop below 1 at any point. Which algorithmic approach guarantees finding the minimum initial health required to survive the dungeon?

easy

A. Dynamic programming starting from the bottom-right cell and moving backward to the top-left

B. Greedy algorithm that always chooses the next cell with the highest health gain

C. Pure brute force recursion exploring all paths from start to end

D. Dijkstra's shortest path algorithm treating health as distance

Solution

1. Step 1: Understand problem constraints

   The problem requires minimum initial health ensuring health never drops below 1, which depends on future cells, so greedy or shortest path won't work.

2. Step 2: Identify correct DP direction

   Starting from the bottom-right cell and moving backward allows computing minimum health needed at each cell based on future states.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Backward DP correctly accounts for future health requirements [OK]

Hint: Backward DP from goal ensures future states known [OK]

Common Mistakes:

• Assuming greedy or forward DP works
• Using shortest path ignoring health constraints

3. What is the time complexity of the bottom-up DP solution for the Cherry Pickup problem on an n x n grid, where dp is a 3D array indexed by step and two row positions of the players?

medium

A. O(4^n) due to exploring all possible paths for two players

B. O(n^3) because there are O(n) steps and O(n^2) states for the two players' rows, each computed in constant time

C. O(n^4) since for each dp state, four previous states are checked

D. O(n^2) as the dp only tracks positions of two players without step dimension

Solution

1. Step 1: Identify number of states

   There are 2n-1 steps, and for each step, possible row positions for player 1 and player 2 are each O(n), so total states are O(n^3).

2. Step 2: Analyze transitions per state

   Each dp state checks up to 4 previous states in O(1) time, so total time is O(n^3).

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   3D dp with O(n^3) states and constant transitions [OK]

Hint: Count states x transitions carefully [OK]

Common Mistakes:

• Confusing number of states with number of transitions
• Assuming exponential time due to recursion
• Ignoring that step dimension limits valid states

4. Suppose the Stone Game is modified so that players can pick stones from either end multiple times (i.e., reuse piles after picking). Which of the following changes correctly adapts the DP solution to handle this variant?

hard

A. Use a bottom-up DP with a sliding window over piles, but do not change the recurrence relation

B. Keep the same interval DP but add a loop to consider picking the same pile multiple times in one turn

C. Change dp state to represent maximum difference with unlimited picks and use a 1D dp array updated iteratively

D. Switch to a greedy approach since DP no longer applies when reuse is allowed

Solution

1. Step 1: Understand the impact of reuse

   Allowing reuse means piles are infinite or replenished, so intervals no longer shrink and the problem resembles unbounded knapsack.

2. Step 2: Adapt DP state and recurrence

   We need a 1D dp array representing maximum difference for each possible pile count, updated iteratively considering unlimited picks, similar to unbounded knapsack.

3. Step 3: Reject incorrect options

   Interval DP with multiple picks per turn or unchanged recurrence won't handle reuse correctly; greedy fails due to opponent's optimal play.

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   Reuse -> unbounded knapsack style DP with 1D array [OK]

Hint: Reuse -> unbounded knapsack DP, not interval DP [OK]

Common Mistakes:

• Trying to reuse interval DP unchanged
• Assuming greedy works with reuse

5. Suppose the Zuma Game variant allows reusing balls from the hand infinitely many times (unlimited supply). Which modification to the algorithm is necessary to correctly compute the minimal insertions?

hard

A. Add a visited set to memoize only board states without hand counts

B. Keep hand_count but reset counts after each recursion to simulate reuse

C. Use greedy insertion since infinite supply guarantees minimal moves by earliest removal

D. Remove hand_count tracking and treat hand as infinite supply; use interval DP without hand state

Solution

1. Step 1: Understand infinite supply impact

   With unlimited balls, hand counts are irrelevant; only board intervals matter.

2. Step 2: Modify DP state and transitions

   Remove hand_count from state and transitions; interval DP can focus solely on board intervals to find minimal insertions.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Infinite supply simplifies state, removing hand count dimension [OK]

Hint: Infinite supply removes hand count dimension [OK]

Common Mistakes:

• Resetting hand counts incorrectly simulates reuse
• Using greedy approach which may not be minimal
• Memoizing without hand counts but missing board state uniqueness