Triangle (Min Path Sum)

▶

Steps

setup

Initialize dp with last row

We start by copying the last row of the triangle into the dp array. This represents the base case where the minimum path sum starting at the bottom row is the element itself.

💡 Initializing dp with the last row sets the foundation for bottom-up calculation, as these values are known and do not depend on any further computations.

Line:

dp = triangle[-1][:]

💡 The dp array now holds the minimum path sums for the bottom row, which are just the values themselves.

fill_row

Start processing row 2 (index 2)

We begin iterating from the second last row (row 2). The active row is now row 2, and we will update dp values for each element in this row.

💡 Processing from bottom to top ensures that dp values for the row below are already computed and can be used to update the current row.

Line:

for i in range(len(triangle) - 2, -1, -1):

💡 The iteration order is crucial for bottom-up DP, starting from the row above the last.

fill_cells

Update dp[0] for row 2

For element 0 in row 2 (value 6), update dp[0] by adding 6 to the minimum of dp[0] and dp[1] from the row below (4 and 1).

💡 Choosing the minimum of the two adjacent dp values below ensures the path sum is minimized.

Line:

dp[j] = triangle[i][j] + min(dp[j], dp[j + 1])

💡 dp[0] is updated to 6 + 1 = 7, representing the minimum path sum starting at element 6.

fill_cells

Update dp[1] for row 2

For element 1 in row 2 (value 5), update dp[1] by adding 5 to the minimum of dp[1] and dp[2] from the row below (1 and 8).

💡 Again, picking the smaller adjacent dp value ensures the path sum remains minimal.

Line:

dp[j] = triangle[i][j] + min(dp[j], dp[j + 1])

💡 dp[1] is updated to 5 + 1 = 6, the minimum path sum starting at element 5.

fill_cells

Update dp[2] for row 2

For element 2 in row 2 (value 7), update dp[2] by adding 7 to the minimum of dp[2] and dp[3] from the row below (8 and 3).

💡 Selecting the smaller adjacent dp value continues the pattern of minimizing path sums.

Line:

dp[j] = triangle[i][j] + min(dp[j], dp[j + 1])

💡 dp[2] is updated to 7 + 3 = 10, representing the minimum path sum starting at element 7.

fill_row

Start processing row 1 (index 1)

Move up to row 1. We will update dp values for this row using the dp array updated from row 2.

💡 Each dp update depends on the two adjacent dp values below, so now dp reflects row 2's minimum path sums.

Line:

for i in range(len(triangle) - 2, -1, -1):

💡 The algorithm continues bottom-up, now focusing on row 1.

fill_cells

Update dp[0] for row 1

For element 0 in row 1 (value 3), update dp[0] by adding 3 to the minimum of dp[0] and dp[1] from row 2 (7 and 6).

💡 Choosing the smaller dp value below ensures the path sum remains minimal.

Line:

dp[j] = triangle[i][j] + min(dp[j], dp[j + 1])

💡 dp[0] is updated to 3 + 6 = 9, the minimum path sum starting at element 3.

fill_cells

Update dp[1] for row 1

For element 1 in row 1 (value 4), update dp[1] by adding 4 to the minimum of dp[1] and dp[2] from row 2 (6 and 10).

💡 Selecting the smaller dp value below continues to minimize the path sum.

Line:

dp[j] = triangle[i][j] + min(dp[j], dp[j + 1])

💡 dp[1] is updated to 4 + 6 = 10, representing the minimum path sum starting at element 4.

fill_row

Start processing row 0 (top row)

Move up to the top row (row 0). We will update dp for the single element in this row using dp values from row 1.

💡 This final update will produce the minimum path sum for the entire triangle.

Line:

for i in range(len(triangle) - 2, -1, -1):

💡 The algorithm is about to compute the final answer at the apex of the triangle.

fill_cells

Update dp[0] for top row

For the top element (value 2), update dp[0] by adding 2 to the minimum of dp[0] and dp[1] from row 1 (9 and 10).

💡 This final step combines all previous computations to find the minimum path sum from top to bottom.

Line:

dp[j] = triangle[i][j] + min(dp[j], dp[j + 1])

💡 dp[0] is updated to 2 + 9 = 11, the minimum path sum for the entire triangle.

reconstruct

Return final answer

The algorithm returns dp[0], which now contains the minimum path sum from the top to the bottom of the triangle.

💡 Returning dp[0] completes the bottom-up DP process, providing the solution without recursion.

Line:

return dp[0]

💡 The final dp[0] value (11) is the minimum path sum for the input triangle.

from typing import List

def minimumTotal(triangle: List[List[int]]) -> int:
    dp = triangle[-1][:]  # STEP 1: Initialize dp with last row
    for i in range(len(triangle) - 2, -1, -1):  # STEP 2,6,9: Iterate from second last row up
        for j in range(len(triangle[i])):
            dp[j] = triangle[i][j] + min(dp[j], dp[j + 1])  # STEP 3-5,7-8,10: Update dp[j]
    return dp[0]  # STEP 11: Return final answer

if __name__ == "__main__":
    tri = [[2],[3,4],[6,5,7],[4,1,8,3]]
    print(minimumTotal(tri))  # Output: 11

📊

Triangle (Min Path Sum) - Watch the Algorithm Execute, Step by Step

Watching the algorithm step-by-step reveals how dynamic programming builds solutions from smaller subproblems, making the minimum path sum clear without complex recursion.

Initializing dp array

i\w	0
i=0	2
i=1	3	4
i=2	6	5	7
i=3	4	1	8	3

dp init

Initializing dp array

i\w	0
i=0	2
i=1	3	4
i=2	6	5	7
i=3	4	1	8	3

processing row 2

Item 0 - wt:6 val:7

i\w	0
i=0	2
i=1	3	4
i=2	7	5	7
i=3	4	1	8	3

updating dp[0]

Item 1 - wt:5 val:6

i\w	0
i=0	2
i=1	3	4
i=2	7	6	7
i=3	4	1	8	3

updating dp[1]

Item 2 - wt:7 val:10

i\w	0
i=0	2
i=1	3	4
i=2	7	6	10
i=3	4	1	8	3

updating dp[2]

Initializing dp array

i\w	0
i=0	2
i=1	3	4
i=2	7	6	10
i=3	4	1	8	3

processing row 1

Item 0 - wt:3 val:9

i\w	0
i=0	2
i=1	9	4
i=2	7	6	10
i=3	4	1	8	3

updating dp[0]

Item 1 - wt:4 val:10

i\w	0
i=0	2
i=1	9	10
i=2	7	6	10
i=3	4	1	8	3

updating dp[1]

Initializing dp array

i\w	0
i=0	2
i=1	9	10
i=2	7	6	10
i=3	4	1	8	3

processing top row

Item 0 - wt:2 val:11

i\w	0
i=0	11
i=1	9	10
i=2	7	6	10
i=3	4	1	8	3

final dp[0]

Item 0 - wt:2 val:11

i\w	0
i=0	11
i=1	9	10
i=2	7	6	10
i=3	4	1	8	3

answer cell

Key Takeaways

✓ Bottom-up DP builds the solution from the known base case at the bottom row upwards.

This insight is hard to see from code alone because the recursion is implicit; watching dp update clarifies the process.

✓ Each dp cell depends only on the two adjacent cells below, showing the overlapping subproblems clearly.

Visualizing dependencies helps understand why the algorithm iterates bottom-up and how it avoids recomputation.

✓ The final answer is stored in dp[0] after processing the top row, representing the minimal path sum from apex to base.

Seeing the final dp array state confirms how the answer emerges from incremental updates.

Practice

1. You are given an array of balloons, each with a number representing coins. When you burst a balloon, you gain coins equal to the product of the balloon's number and its adjacent balloons' numbers. After bursting, the balloon disappears and adjacent balloons become neighbors. Which algorithmic approach guarantees finding the maximum coins you can collect by bursting all balloons in an optimal order?

easy

A. Greedy approach bursting the balloon with the highest number first

B. Sorting balloons and bursting them in ascending order

C. Dynamic programming using interval partitioning and considering the last balloon to burst in each interval

D. Simple recursion trying all burst orders without memoization

Solution

1. Step 1: Understand problem structure

   The problem requires maximizing coins by bursting balloons in an order where each burst depends on adjacent balloons, which changes dynamically.

2. Step 2: Identify suitable algorithm

   Greedy or sorting approaches fail because local choices don't guarantee global optimum. Simple recursion is correct but inefficient. Interval DP solves by considering subproblems defined by intervals and choosing the last balloon to burst in each interval, ensuring optimal substructure.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Interval DP handles overlapping subproblems and changing neighbors [OK]

Hint: Optimal substructure requires interval DP, not greedy [OK]

Common Mistakes:

• Assuming greedy bursting yields max coins
• Trying recursion without memoization
• Ignoring interval-based subproblems

2. Given the following code for finding the cheapest flight within K stops, what is the returned value for the input below? Input: n = 3 flights = [[0,1,100],[1,2,100],[0,2,500]] src = 0 dst = 2 K = 1

def findCheapestPrice(n, flights, src, dst, K):
    INF = float('inf')
    prev = [INF] * n
    prev[src] = 0
    for _ in range(K + 1):
        curr = prev[:]
        for u, v, w in flights:
            if prev[u] != INF:
                curr[v] = min(curr[v], prev[u] + w)
        prev = curr
    return prev[dst] if prev[dst] != INF else -1

print(findCheapestPrice(n, flights, src, dst, K))

easy

A. 500

B. 200

C. -1

D. 100

Solution

1. Step 1: Trace dp arrays for each iteration

   Initially prev = [0, inf, inf]. After first iteration (0 stops), curr updates cost to city 1 as 100 and city 2 as 500. After second iteration (1 stop), curr updates city 2 cost to min(500, 100 + 100) = 200.

2. Step 2: Return final cost for destination

   prev[2] after K+1=2 iterations is 200, which is the cheapest cost with at most 1 stop.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   DP updates costs correctly over K+1 iterations [OK]

Hint: DP updates cost over K+1 iterations [OK]

Common Mistakes:

• Returning direct edge cost ignoring stops
• Off-by-one in iteration count
• Confusing curr and prev arrays

3. Consider the following bottom-up DP code for the Strange Printer problem. What is the final returned value when the input string is "aba"?

easy

A. 3

B. 4

C. 1

D. 2

Solution

1. Step 1: Compress input string "aba"

   Compression does not change string since no consecutive duplicates: s = "aba", n=3.

2. Step 2: Trace dp table filling

   Base cases: dp[0][0]=1, dp[1][1]=1, dp[2][2]=1. For length=2: - dp[0][1]: dp[0][0]+1=2, s[0]!=s[1], so dp[0][1]=2 - dp[1][2]: dp[1][1]+1=2, s[1]!=s[2], so dp[1][2]=2 For length=3: - dp[0][2]: dp[0][1]+1=3 Check k=0: s[0]==s[2] ('a'=='a'), dp[0][0]+dp[1][1]=1+1=2 < 3, so dp[0][2]=2

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Output matches known minimal turns for "aba" [OK]

Hint: Check dp merging when s[k] == s[j] reduces turns [OK]

Common Mistakes:

• Forgetting to merge intervals when characters match

4. What is the time complexity of the space-optimized bottom-up DP solution for the Cheapest Flights Within K Stops problem, given n cities, E flights, and maximum K stops?

medium

A. O(K * E) because each iteration relaxes all edges up to K+1 times

B. O(n^3) due to nested loops over cities and stops

C. O(E * log n) similar to Dijkstra's algorithm

D. O(n * K^2) due to dynamic programming over stops and cities

Solution

1. Step 1: Identify loops in the algorithm

   The outer loop runs K+1 times, and the inner loop iterates over all E flights to relax edges.

2. Step 2: Calculate total complexity

   Each iteration processes E edges, so total time is O(K * E). No nested loops over n^2 or log factors appear.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Algorithm iterates over edges K+1 times [OK]

Hint: Outer loop K+1 times, inner loop over E edges [OK]

Common Mistakes:

• Confusing E with n^2
• Assuming Dijkstra complexity
• Counting recursion stack space

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