Minimum Path Sum

▶

Steps

setup

Initialize dp array size

We determine the number of rows (m) and columns (n) in the grid and create a dp array of length n initialized with zeros.

💡 Knowing the grid dimensions and preparing dp storage is the foundation for the bottom-up computation.

Line:

m, n = len(grid), len(grid[0])
dp = [0]*n

💡 The dp array length matches the number of columns, enabling row-wise updates.

setup

Set dp[0] to grid[0][0]

Initialize the first element of dp with the top-left grid value, as the path starts here.

💡 This sets the base case for the path sum at the starting cell.

Line:

dp[0] = grid[0][0]

💡 The minimum path sum to the first cell is simply its own value.

fill_row

Fill dp for first row cumulatively (j=1)

Update dp[1] by adding grid[0][1] to dp[0], accumulating the path sum moving right.

💡 Filling the first row dp values shows how the path sum accumulates when moving only right.

Line:

for j in range(1, n):
    dp[j] = dp[j-1] + grid[0][j]

💡 The minimum path sum to cell (0,1) is the sum of the path to (0,0) plus the current cell value.

fill_row

Fill dp for first row cumulatively (j=2)

Update dp[2] by adding grid[0][2] to dp[1], continuing cumulative sums for the first row.

💡 Completing the first row dp array shows the path sums when moving only right across the top row.

Line:

dp[j] = dp[j-1] + grid[0][j]

💡 The minimum path sum to cell (0,2) accumulates all previous values in the first row.

fill_cells

Start processing second row: update dp[0]

Add grid[1][0] to dp[0], updating the minimum path sum for the first column of the second row.

💡 Updating dp[0] reflects moving down from the cell above in the first column.

Line:

for i in range(1, m):
    dp[0] += grid[i][0]

💡 The minimum path sum to cell (1,0) is the sum of the path to (0,0) plus the current cell value.

fill_cells

Update dp[1] for second row

Calculate dp[1] as grid[1][1] plus the minimum of dp[1] (above) and dp[0] (left).

💡 Choosing the minimum between coming from above or left ensures the path sum is minimized.

Line:

for j in range(1, n):
    dp[j] = grid[i][j] + min(dp[j], dp[j-1])

💡 The path to (1,1) is best reached from the left cell (1,0) with sum 2 rather than from above (0,1) with sum 4.

fill_cells

Update dp[2] for second row

Calculate dp[2] as grid[1][2] plus the minimum of dp[2] (above) and dp[1] (left).

💡 Again, we pick the minimum path sum from the two possible directions to minimize total cost.

Line:

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

💡 The path to (1,2) is better from above (0,2) with sum 5 than from left (1,1) with sum 7.

fill_cells

Start processing third row: update dp[0]

Add grid[2][0] to dp[0], updating the minimum path sum for the first column of the third row.

💡 Moving down in the first column accumulates the path sum from above.

Line:

dp[0] += grid[i][0]

💡 The minimum path sum to cell (2,0) accumulates from the previous row's first column.

fill_cells

Update dp[1] for third row

Calculate dp[1] as grid[2][1] plus the minimum of dp[1] (above) and dp[0] (left).

💡 Choosing the minimum path sum from above or left continues to build the optimal path.

Line:

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

💡 The path to (2,1) is better from left (2,0) with sum 6 than from above (1,1) with sum 7.

fill_cells

Update dp[2] for third row

Calculate dp[2] as grid[2][2] plus the minimum of dp[2] (above) and dp[1] (left).

💡 Final update completes the dp array with the minimum path sums for the last row.

Line:

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

💡 The minimum path sum to the bottom-right corner is 7, the smallest possible sum.

reconstruct

Return final minimum path sum

Return the last element of dp, which holds the minimum path sum to the bottom-right corner.

💡 The final dp value is the answer to the problem.

Line:

return dp[-1]

💡 The algorithm efficiently computes the minimum path sum using only a 1D dp array.

def minPathSum(grid):
    m, n = len(grid), len(grid[0])  # STEP 1
    dp = [0]*n  # STEP 1
    dp[0] = grid[0][0]  # STEP 2
    for j in range(1, n):  # STEP 3-4
        dp[j] = dp[j-1] + grid[0][j]
    for i in range(1, m):  # STEP 5-10
        dp[0] += grid[i][0]  # STEP 5,8
        for j in range(1, n):  # STEP 6-7,9-10
            dp[j] = grid[i][j] + min(dp[j], dp[j-1])
    return dp[-1]  # STEP 11

📊

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

Watching each update to the dp array reveals how the algorithm accumulates minimum sums and why it only needs one dimension of storage.

Item 0 - wt:0 val:0

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

Item 0 - wt:1 val:1

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

start

Item 0 - wt:3 val:4

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

update

Item 0 - wt:1 val:5

i\w	0	1	2
i=0	1	4	5

update

Item 1 - wt:1 val:2

i\w	0	1	2
i=0	2	4	5

down move

Item 1 - wt:5 val:7

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

min choice

Item 1 - wt:1 val:6

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

min choice

Item 2 - wt:4 val:6

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

down move

Item 2 - wt:2 val:8

i\w	0	1	2
i=0	6	8	6

min choice

Item 2 - wt:1 val:7

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

final answer

Item 2 - wt:1 val:7

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

answer

Key Takeaways

✓ The algorithm uses a single 1D dp array to store minimum path sums for each column, updating it row by row.

This insight is hard to see from code alone because the dp array is reused and overwritten, but the visualization shows its evolution clearly.

✓ Each dp cell update depends on the minimum of the value above (previous dp[j]) and the value to the left (dp[j-1]), reflecting allowed moves.

Seeing these dependencies visually helps understand why the algorithm chooses the minimum path at each step.

✓ The final answer is the last element of the dp array after processing all rows, representing the minimum path sum to the bottom-right corner.

The visualization clarifies why returning dp[-1] gives the correct answer, which might be less obvious from code alone.

Practice

1. Given the following code for the Dungeon Game problem, what is the value of dp[0][0] returned by calculateMinimumHP when called with dungeon = [[-2,-3,3],[-5,-10,1],[10,30,-5]]?

from typing import List

class Solution:
    def calculateMinimumHP(self, dungeon: List[List[int]]) -> int:
        m, n = len(dungeon), len(dungeon[0])
        dp = [[float('inf')] * (n + 1) for _ in range(m + 1)]
        dp[m][n - 1] = 1
        dp[m - 1][n] = 1

        for i in range(m - 1, -1, -1):
            for j in range(n - 1, -1, -1):
                need = min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j]
                dp[i][j] = max(1, need)

        return dp[0][0]

easy

A. 7

B. 5

C. 3

D. 1

Solution

1. Step 1: Initialize dp boundaries

   dp[3][2] and dp[2][3] set to 1, others infinity.

2. Step 2: Compute dp bottom-up

   Calculate dp values from bottom-right to top-left considering dungeon values and ensuring health ≥1.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Known example output is 7 for this input [OK]

Hint: Trace dp from bottom-right to top-left [OK]

Common Mistakes:

• Off-by-one errors in dp indices
• Forgetting max(1, need)

2. You need to paint n houses, each with one of k colors. Adjacent houses cannot share the same color. Each color choice has a cost per house. Which algorithmic approach guarantees finding the minimum total painting cost efficiently?

easy

A. Dynamic Programming that tracks minimum costs per house and color, avoiding same-color adjacency

B. Depth-first search exploring all color combinations without memoization

C. Greedy algorithm choosing the cheapest color for each house independently

D. Sorting houses by cost and assigning colors in ascending order

Solution

1. Step 1: Understand problem constraints

   The problem requires minimizing total cost with the constraint that no two adjacent houses share the same color.

2. Step 2: Identify suitable algorithm

   Greedy fails because local cheapest choice may cause conflicts later. DFS without memoization is exponential. Sorting houses by cost ignores adjacency constraints. DP tracks costs per house and color, ensuring constraints and optimal substructure.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   DP explicitly handles adjacency and cost minimization [OK]

Hint: DP tracks costs per house and color with adjacency constraints [OK]

Common Mistakes:

• Assuming greedy choice is globally optimal
• Ignoring adjacency constraints in sorting
• Not using memoization in recursion

3. Consider the following Python code for computing unique paths in a grid:

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

print(uniquePaths(3, 3))

What is the value of dp after the outer loop completes its second iteration (i=2)?

easy

A. [1, 3, 6]

B. [1, 2, 3]

C. [1, 3, 5]

D. [1, 4, 10]

Solution

1. Step 1: Initialize dp array

   Initially, dp = [1, 1, 1] for n=3.

2. Step 2: Trace iterations

   First outer iteration (i=1): - j=1: dp[1] = dp[1] + dp[0] = 1 + 1 = 2 - j=2: dp[2] = dp[2] + dp[1] = 1 + 2 = 3 After i=1, dp = [1, 2, 3] Second outer iteration (i=2): - j=1: dp[1] = dp[1] + dp[0] = 2 + 1 = 3 - j=2: dp[2] = dp[2] + dp[1] = 3 + 3 = 6 After i=2, dp = [1, 3, 6]

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   dp array accumulates path counts correctly -> [1,3,6] [OK]

Hint: Track dp updates carefully per iteration [OK]

Common Mistakes:

• Off-by-one errors in loop indices
• Mis-updating dp[j] with wrong dp[j-1] value

4. Identify the bug in the following code snippet for minimum score triangulation of a polygon:

medium

A. Line missing dp[i][j] = float('inf') before minimization

B. Line initializing dp array with zeros

C. Loop boundaries for k from i+1 to j-1

D. Return statement returning dp[0][n-1]

Solution

1. Step 1: Check dp initialization inside loops

   dp[i][j] must be set to infinity before checking for minimal cost; otherwise, dp[i][j] starts at 0 and may never update correctly.

2. Step 2: Confirm other lines are correct

   dp array initialization, loop boundaries, and return statement are correct and standard.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Without dp[i][j] = float('inf'), minimal cost calculation is incorrect [OK]

Hint: Always initialize dp[i][j] before minimization [OK]

Common Mistakes:

• Forgetting dp initialization
• Off-by-one in loops
• Mixing indices i,j,k

5. What is the time complexity of the bottom-up DP solution for the Strange Printer problem after string compression, where m is the length of the compressed string?

medium

A. O(m^2)

B. O(m^3)

C. O(n^3) where n is original string length

D. O(m^2 * log m)

Solution

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

   There are three nested loops: length (1 to m), start index i (up to m), and partition index k (between i and j), each up to m.

2. Step 2: Calculate complexity

   Overall complexity is O(m * m * m) = O(m^3). Compression reduces n to m, so complexity depends on compressed length.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Three nested loops over compressed length m [OK]

Hint: Three nested loops over compressed string length cause cubic time [OK]

Common Mistakes:

• Confusing original length n with compressed length m
• Forgetting the inner loop over k