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. 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

2. Consider the following code for minimum score triangulation of a polygon with vertex values [1, 3, 1, 4]. What is the final returned value?

easy

A. 7

B. 12

C. 10

D. 13

Solution

1. Step 1: Trace dp for length=3 (triangles)

   For i=0,j=2: dp[0][2] = 1*3*1=3; for i=1,j=3: dp[1][3] = 3*1*4=12

2. Step 2: Trace dp for length=4 (whole polygon)

   For i=0,j=3, k=1: cost=dp[0][1]+dp[1][3]+1*3*4=0+12+12=24; k=2: cost=dp[0][2]+dp[2][3]+1*1*4=3+0+4=7; dp[0][3]=7

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Minimal triangulation cost is 7, not 9 or higher [OK]

Hint: Check all k splits for minimal dp[i][j] cost [OK]

Common Mistakes:

• Off-by-one in loops
• Ignoring dp initialization
• Wrong triangle cost calculation

3. What is the time complexity of the bottom-up dynamic programming solution for the Dungeon Game problem on an m x n grid, and why might some candidates mistakenly think it is higher?

medium

A. O(2^{m+n}) because all paths are explored recursively

B. O(m + n) since only one path is considered at a time

C. O(m * n * max(|dungeon[i][j]|)) due to health value range affecting computations

D. O(m * n) because each cell is computed once using constant time operations

Solution

1. Step 1: Identify loops

   The bottom-up DP uses nested loops over m rows and n columns, each cell computed once.

2. Step 2: Analyze per-cell work

   Each dp[i][j] calculation is O(1), involving min and max operations.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   DP table size m*n and constant work per cell [OK]

Hint: DP fills m*n table once, no recursion overhead [OK]

Common Mistakes:

• Confusing brute force recursion with DP
• Thinking health values affect complexity

4. What is the time complexity of the bottom-up dynamic programming solution for the minimum score triangulation of a polygon with n vertices?

medium

A. O(n^2)

B. O(n^4)

C. O(n^3)

D. O(n^3 * log n)

Solution

1. Step 1: Identify loops in the code

   There are three nested loops: length (up to n), i (up to n), and k (up to n), each iterating up to n times.

2. Step 2: Calculate total complexity

   Multiplying these loops gives O(n * n * n) = O(n^3). No extra log factor or higher power arises.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Three nested loops over n vertices -> cubic time [OK]

Hint: Count nested loops carefully to avoid underestimating complexity [OK]

Common Mistakes:

• Confusing recursion stack space
• Assuming only two nested loops
• Adding unnecessary log factors

5. 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