Minimum Falling Path Sum

▶

Steps

setup

Initialize dp with first row

We start by copying the first row of the matrix into the dp array. This represents the minimum path sums for the first row, which are just the values themselves.

💡 Initializing dp with the first row sets the base case for the dynamic programming solution.

Line:

dp = matrix[0][:]

💡 The dp array now holds the minimum sums for the first row, serving as the foundation for subsequent calculations.

fill_row

Start processing second row: initialize new_dp

We begin processing the second row by creating a new_dp array initialized with zeros to store updated minimum path sums.

💡 Preparing a new array for the current row allows us to compute new values without overwriting the previous dp array.

Line:

new_dp = [0]*n

💡 new_dp will hold the minimum sums for the second row after considering adjacent cells from dp.

fill_cells

Compute new_dp[0] using dp[0] and dp[1]

For column 0 in the second row, we consider dp[0] and dp[1] from the previous row to find the minimum adjacent path sum, then add matrix[1][0].

💡 Checking adjacent cells ensures we only consider valid falling paths from the previous row.

Line:

best = dp[j]
if j > 0:
  best = min(best, dp[j-1])

💡 The minimum adjacent sum for new_dp[0] is 1 from dp[1], showing adjacency matters.

fill_cells

Compute new_dp[1] using dp[0], dp[1], dp[2]

For column 1 in the second row, we consider dp[0], dp[1], and dp[2] to find the minimum adjacent path sum, then add matrix[1][1].

💡 Including three adjacent cells covers all possible falling paths to this position.

Line:

best = dp[j]
if j > 0:
  best = min(best, dp[j-1])
if j < n - 1:
  best = min(best, dp[j+1])

💡 The minimum adjacent sum for new_dp[1] is 1 from dp[1], showing the center cell is best here.

fill_cells

Compute new_dp[2] using dp[1] and dp[2]

For column 2 in the second row, we consider dp[1] and dp[2] from the previous row to find the minimum adjacent path sum, then add matrix[1][2].

💡 For the last column, only two adjacent cells are valid to consider.

Line:

best = dp[j]
if j > 0:
  best = min(best, dp[j-1])

💡 The minimum adjacent sum for new_dp[2] is 1 from dp[1], showing adjacency limits at edges.

fill_row

Update dp with new_dp for second row

After computing all columns for the second row, we update dp to new_dp to prepare for the next iteration.

💡 Updating dp allows the algorithm to use the latest minimum sums for the next row's calculations.

Line:

dp = new_dp

💡 dp now holds the minimum falling path sums up to the second row.

fill_row

Start processing third row: initialize new_dp

We start processing the third row by creating a new_dp array initialized with zeros to store updated minimum path sums.

💡 Again, a fresh array is needed to compute the current row's results without overwriting dp prematurely.

Line:

new_dp = [0]*n

💡 new_dp will hold the minimum sums for the third row after considering dp.

fill_cells

Compute new_dp[0] using dp[0] and dp[1]

For column 0 in the third row, we consider dp[0] and dp[1] to find the minimum adjacent path sum, then add matrix[2][0].

💡 We again consider only valid adjacent cells for the first column.

Line:

best = dp[j]
if j > 0:
  best = min(best, dp[j-1])

💡 The minimum adjacent sum for new_dp[0] is 6 from dp[1], showing how the path sum accumulates.

fill_cells

Compute new_dp[1] using dp[0], dp[1], dp[2]

For column 1 in the third row, we consider dp[0], dp[1], and dp[2] to find the minimum adjacent path sum, then add matrix[2][1].

💡 Considering three adjacent cells covers all possible falling paths to this position.

Line:

best = dp[j]
if j > 0:
  best = min(best, dp[j-1])
if j < n - 1:
  best = min(best, dp[j+1])

💡 The minimum adjacent sum for new_dp[1] is 5 from dp[2], showing the best path can come from the right.

fill_cells

Compute new_dp[2] using dp[1] and dp[2]

For column 2 in the third row, we consider dp[1] and dp[2] to find the minimum adjacent path sum, then add matrix[2][2].

💡 For the last column, only two adjacent cells are valid to consider.

Line:

best = dp[j]
if j > 0:
  best = min(best, dp[j-1])

💡 The minimum adjacent sum for new_dp[2] is 5 from dp[2], showing adjacency limits at edges.

fill_row

Update dp with new_dp for third row

After computing all columns for the third row, we update dp to new_dp to prepare for the final answer extraction.

💡 Updating dp completes the dynamic programming computation for all rows.

Line:

dp = new_dp

💡 dp now holds the minimum falling path sums for the entire matrix.

traverse

Find minimum value in dp

We scan the dp array to find the minimum value, which represents the minimum falling path sum for the entire matrix.

💡 The final answer is the smallest sum in dp after processing all rows.

Line:

return min(dp)

💡 The minimum falling path sum is 13, confirming the path 1 → 5 → 7.

def minFallingPathSum(matrix):
    n = len(matrix)
    dp = matrix[0][:]  # STEP 1: Initialize dp with first row

    for i in range(1, n):  # STEP 2,6,7,11: Process each subsequent row
        new_dp = [0]*n  # STEP 2,7: Initialize new_dp
        for j in range(n):  # STEP 3-5,8-10: Compute new_dp[j]
            best = dp[j]  # STEP 3,4,5,8,9,10: Start with dp[j]
            if j > 0:
                best = min(best, dp[j-1])  # STEP 3,4,5,8,9,10: Check left neighbor
            if j < n - 1:
                best = min(best, dp[j+1])  # STEP 4,5,9: Check right neighbor
            new_dp[j] = matrix[i][j] + best  # STEP 3-5,8-10: Update new_dp[j]
        dp = new_dp  # STEP 6,11: Update dp

    return min(dp)  # STEP 12: Return minimum value in dp

📊

Minimum Falling Path Sum - Watch the Algorithm Execute, Step by Step

Watching each update to the dp array reveals how the algorithm builds solutions from the top row down, making the dynamic programming approach intuitive and clear.

Item 0 - wt:2 val:2

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

dp[0] = 2

Item 1 - wt:6 val:6

i\w	0	1	2
i=0	2	1	3
i=1	?	?	?

new_dp initialized

Item 1 - wt:6 val:6

i\w	0	1	2
i=0	2	1	3
i=1	7	?	?

dp[0] = 2

Item 1 - wt:5 val:5

i\w	0	1	2
i=0	2	1	3
i=1	7	6	?

dp[0] = 2

Item 1 - wt:4 val:4

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

dp[1] = 1

Item 1 - wt:0 val:0

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

dp[0] = 7

Item 2 - wt:7 val:7

i\w	0	1	2
i=0	2	1	3
i=1	7	6	5
i=2	?	?	?

new_dp initialized

Item 2 - wt:7 val:7

i\w	0	1	2
i=0	2	1	3
i=1	7	6	5
i=2	13	?	?

dp[0] = 7

Item 2 - wt:8 val:8

i\w	0	1	2
i=0	2	1	3
i=1	7	6	5
i=2	13	13	?

dp[0] = 7

Item 2 - wt:9 val:9

i\w	0	1	2
i=0	2	1	3
i=1	7	6	5
i=2	13	13	14

dp[1] = 6

Item 2 - wt:0 val:0

i\w	0	1	2
i=0	2	1	3
i=1	7	6	5
i=2	13	13	14

dp[0] = 13

Item 2 - wt:0 val:0

i\w	0	1	2
i=0	2	1	3
i=1	7	6	5
i=2	13	13	14

min dp = 13

Key Takeaways

✓ The dp array represents the minimum falling path sums up to the current row, updated iteratively.

This insight is hard to see from code alone because the dp array is overwritten each iteration, but watching the visualization shows its evolving meaning.

✓ Each cell in the current row depends only on up to three adjacent cells from the previous row, reflecting the falling path constraints.

Visualizing these dependencies clarifies why only adjacent cells are considered, which might be confusing from code alone.

✓ The final answer is the minimum value in the dp array after processing all rows, representing the minimum falling path sum.

Seeing the final dp array and the answer cell highlighted helps concretely connect the algorithm's output to the dp state.

Practice

1. Consider the following Python function implementing the bottom-up DP solution for the Burst Balloons problem. What is the value of dp[1][4] after the completion of the outer loops when the input is [3,1,5,8]?

def maxCoins(nums):
    n = len(nums)
    nums = [1] + nums + [1]
    dp = [[0] * (n + 2) for _ in range(n + 2)]
    for length in range(2, n + 2):
        for i in range(0, n + 2 - length):
            j = i + length
            for k in range(i + 1, j):
                coins = dp[i][k] + nums[i] * nums[k] * nums[j] + dp[k][j]
                if coins > dp[i][j]:
                    dp[i][j] = coins
    return dp[0][n + 1]

easy

A. 15

B. 45

C. 40

D. 167

Solution

1. Step 1: Identify dp indices

   dp[1][4] corresponds to bursting balloons in nums indices 1 to 3 (original array indices 0 to 2), i.e. balloons [3,1,5].

2. Step 2: Calculate dp[1][4]

   By bursting last balloon k in (1,4), check k=2 and k=3: - k=2: dp[1][2] + nums[1]*nums[2]*nums[4] + dp[2][4] = 0 + 3*1*8 + 40 = 64 - k=3: dp[1][3] + nums[1]*nums[3]*nums[4] + dp[3][4] = 15 + 3*5*8 + 0 = 135 Max is 135, so dp[1][4] = 135 after the loops.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   dp[1][4] = 135 matches manual calculation [OK]

Hint: dp[i][j] stores max coins for bursting balloons between i and j [OK]

Common Mistakes:

• Confusing dp indices with nums indices
• Off-by-one errors in loops
• Miscomputing coins for k choices

2. You have a grid where two players start at the top-left corner and move to the bottom-right corner simultaneously, collecting cherries on their paths. Both players can only move right or down, and some cells contain thorns that block passage. The goal is to maximize the total cherries collected by both players without double-counting cherries if they land on the same cell. Which algorithmic approach guarantees finding the optimal solution for this problem?

easy

A. Greedy algorithm that always picks the next cell with the most cherries for each player independently.

B. Divide and conquer by splitting the grid into two halves and solving each half independently.

C. Dynamic programming that tracks both players' positions simultaneously and uses a 3D state to avoid double counting and invalid paths.

D. Simple BFS traversal from start to end for each player separately, then summing their maximum cherries.

Solution

1. Step 1: Understand the problem constraints

   Two players move simultaneously on the grid, collecting cherries without double counting and avoiding thorns. Both must take the same number of steps at any point.

2. Step 2: Identify the suitable algorithmic pattern

   Dynamic programming with a 3D state (step count and both players' row positions) tracks both players' positions simultaneously, ensuring valid states and avoiding double counting.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   DP with simultaneous states handles constraints correctly [OK]

Hint: Two simultaneous paths require joint DP state [OK]

Common Mistakes:

• Assuming independent paths and summing results
• Using greedy to pick local max cherries
• Splitting grid and solving halves independently

3. What is the time complexity of the optimal bottom-up DP solution for the Paint House (K Colors) problem with n houses and k colors?

medium

A. O(n * k)

B. O(n^2 * k)

C. O(k^n)

D. O(n * k * k)

Solution

1. Step 1: Identify loops in the DP solution

   The outer loop runs over n houses, the inner loop over k colors, and inside that, a min over k colors excluding current color is computed, resulting in k iterations.

2. Step 2: Calculate total complexity

   Total operations = n (houses) * k (colors) * k (min over colors) = O(n * k * k). The recursion stack or auxiliary space does not add to time complexity here.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Nested loops over n, k, and k confirm O(n*k*k) [OK]

Hint: Remember min over k colors inside k-loop -> O(n*k*k) [OK]

Common Mistakes:

• Assuming O(n*k) ignoring inner min loop
• Confusing exponential brute force with DP
• Mistaking recursion stack space for time

4. The following code attempts to compute the number of unique paths in an m x n grid using a space-optimized DP approach:

def uniquePaths(m, n):
    dp = [1] * n
    for i in range(1, m):
        for j in range(1, n):
            dp[j] = dp[j] + dp[j]
    return dp[-1]

What is the bug in this code?

medium

A. Line 3 should start loop from 0 instead of 1

B. Line 4 incorrectly doubles dp[j] instead of adding dp[j-1]

C. Line 5 should return dp[0] instead of dp[-1]

D. Line 2 initializes dp with wrong size

Solution

1. Step 1: Analyze inner loop update

   Line 4 updates dp[j] by adding dp[j] to itself, doubling the value instead of adding dp[j-1].

2. Step 2: Identify correct update

   The correct update is dp[j] += dp[j - 1] to accumulate paths from left and top cells.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Doubling dp[j] breaks path count logic -> bug at line 4 [OK]

Hint: Check dp update uses dp[j-1], not dp[j] twice [OK]

Common Mistakes:

• Using dp[j] + dp[j] instead of dp[j] + dp[j-1]
• Off-by-one errors in loops

5. Suppose the grid can contain negative numbers, and you want to find the minimum path sum from top-left to bottom-right moving only down or right. Which modification to the space-optimized DP approach is necessary to handle this correctly?

hard

A. Use the same DP approach since negative numbers do not affect correctness

B. Switch to a BFS or Dijkstra's algorithm to handle negative weights properly

C. Use top-down memoization with cycle detection to avoid infinite loops

D. Modify DP to track visited states and prevent revisiting cells

Solution

1. Step 1: Understand impact of negative numbers

   Negative numbers can create cycles with decreasing path sums if revisiting cells is allowed, causing infinite recursion.

2. Step 2: Recognize that moving only down or right prevents cycles

   Since moves are restricted to down or right, no cycles exist, so DP can still work, but negative values can cause incorrect min calculations if not handled carefully.

3. Step 3: Consider top-down memoization with cycle detection

   To be safe and handle any relaxed constraints (e.g., allowing revisits), top-down with memoization and cycle detection is necessary to avoid infinite loops.

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   Memoization with cycle detection prevents infinite recursion with negative weights [OK]

Hint: Negative weights require cycle detection in recursive solutions [OK]

Common Mistakes:

• Assuming DP always works with negative numbers
• Using BFS/Dijkstra without graph edges
• Ignoring possibility of cycles with negative weights