Unique Paths

▶

Steps

setup

Initialize DP array with 1s

Create a 1D DP array of length n=7, initializing all elements to 1. This represents the first row where there is exactly one way to reach each cell by moving only right.

💡 Initializing with 1s sets the base case: from the top-left corner, there is only one path to any cell in the first row.

Line:

dp = [1] * n

💡 The DP array starts with all 1s because the first row's path counts are straightforward and serve as the foundation for subsequent rows.

fill_row

Start processing row 1 (second row)

Begin iterating over the second row (i=1). The DP array currently holds path counts for the first row.

💡 Processing the second row updates the DP array to reflect paths including moves down from the first row.

Line:

for i in range(1, m):

💡 The outer loop controls which row is being processed, starting from the second row.

fill_cells

Update dp[1] for row 1

Update dp[1] by adding dp[0] to dp[1]: dp[1] = dp[1] + dp[0] = 1 + 1 = 2. This counts paths from left and above.

💡 Each dp[j] accumulates paths from the left (dp[j-1]) and from above (dp[j]) to count all unique paths to that cell.

Line:

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

💡 The update reflects that the number of paths to cell (1,1) is the sum of paths to (1,0) and (0,1).

fill_cells

Update dp[2] for row 1

Update dp[2] by adding dp[1] to dp[2]: dp[2] = dp[2] + dp[1] = 1 + 2 = 3.

💡 This step continues accumulating paths for the second row, combining left and above paths.

Line:

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

💡 The value dp[2] now represents all unique paths to cell (1,2).

fill_cells

Update dp[3] for row 1

Update dp[3] by adding dp[2] to dp[3]: dp[3] = dp[3] + dp[2] = 1 + 3 = 4.

💡 Continuing the accumulation of unique paths for the second row.

Line:

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

💡 dp[3] now counts all unique paths to cell (1,3).

fill_cells

Update dp[4] for row 1

Update dp[4] by adding dp[3] to dp[4]: dp[4] = dp[4] + dp[3] = 1 + 4 = 5.

💡 Each dp[j] update sums paths from left and above to build the total unique paths.

Line:

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

💡 dp[4] now holds the count of unique paths to cell (1,4).

fill_cells

Update dp[5] for row 1

Update dp[5] by adding dp[4] to dp[5]: dp[5] = dp[5] + dp[4] = 1 + 5 = 6.

💡 The DP array continues to accumulate path counts moving right.

Line:

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

💡 dp[5] now represents unique paths to cell (1,5).

fill_cells

Update dp[6] for row 1

Update dp[6] by adding dp[5] to dp[6]: dp[6] = dp[6] + dp[5] = 1 + 6 = 7.

💡 Final update for the second row completes the DP array for this iteration.

Line:

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

💡 dp[6] now holds the total unique paths to cell (1,6).

fill_row

Start processing row 2 (third row)

Begin iterating over the third row (i=2). The DP array currently holds path counts for the second row.

💡 Processing the third row updates the DP array to reflect paths including moves down from the second row.

Line:

for i in range(1, m):

💡 The outer loop moves to the last row to update path counts accordingly.

fill_cells

Update dp[1] for row 2

Update dp[1] by adding dp[0] to dp[1]: dp[1] = dp[1] + dp[0] = 2 + 1 = 3.

💡 Start accumulating paths for the third row by combining left and above paths.

Line:

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

💡 dp[1] now counts all unique paths to cell (2,1).

fill_cells

Update dp[2] for row 2

Update dp[2] by adding dp[1] to dp[2]: dp[2] = dp[2] + dp[1] = 3 + 3 = 6.

💡 Continuing accumulation for the third row.

Line:

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

💡 dp[2] now holds the count of unique paths to cell (2,2).

fill_cells

Update dp[3] for row 2

Update dp[3] by adding dp[2] to dp[3]: dp[3] = dp[3] + dp[2] = 4 + 6 = 10.

💡 Accumulating paths for cell (2,3).

Line:

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

💡 dp[3] now represents unique paths to cell (2,3).

fill_cells

Update dp[4] for row 2

Update dp[4] by adding dp[3] to dp[4]: dp[4] = dp[4] + dp[3] = 5 + 10 = 15.

💡 Continuing to accumulate paths for the third row.

Line:

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

💡 dp[4] now holds the count of unique paths to cell (2,4).

fill_cells

Update dp[5] for row 2

Update dp[5] by adding dp[4] to dp[5]: dp[5] = dp[5] + dp[4] = 6 + 15 = 21.

💡 Accumulating paths for cell (2,5).

Line:

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

💡 dp[5] now represents unique paths to cell (2,5).

fill_cells

Update dp[6] for row 2

Update dp[6] by adding dp[5] to dp[6]: dp[6] = dp[6] + dp[5] = 7 + 21 = 28.

💡 Final update for the third row completes the DP array for this iteration.

Line:

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

💡 dp[6] now holds the total unique paths to the bottom-right corner (2,6).

reconstruct

Return final answer

Return dp[-1], which is dp[6] = 28, representing the total unique paths from top-left to bottom-right.

💡 The last element in the DP array holds the final answer after processing all rows.

Line:

return dp[-1]

💡 The algorithm efficiently computes the answer using a single 1D DP array updated row by row.

def uniquePaths(m, n):
    dp = [1] * n  # STEP 1: Initialize dp array with 1s
    for i in range(1, m):  # STEP 2, 9: Iterate over rows starting from second
        for j in range(1, n):  # STEP 3-8, 10-15: Update dp[j] for each column
            dp[j] += dp[j - 1]  # STEP: Update dp[j] by adding dp[j-1]
    return dp[-1]  # STEP 16: Return final answer

if __name__ == '__main__':
    print(uniquePaths(3, 7))  # Output: 28

📊

Unique Paths - Watch the Algorithm Execute, Step by Step

Watching each update in the DP array reveals how the solution builds on previous results, making the dynamic programming approach intuitive and clear.

Item 0 - wt:7 val:1

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

Initialized to 1

Item 1 - wt:7 val:1

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

DP before row 1 updates

Item 1 - wt:7 val:2

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

Updating dp[1]

Item 1 - wt:7 val:3

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

Updating dp[2]

Item 1 - wt:7 val:4

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

Updating dp[3]

Item 1 - wt:7 val:5

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

Updating dp[4]

Item 1 - wt:7 val:6

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

Updating dp[5]

Item 1 - wt:7 val:7

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

Updating dp[6]

Item 2 - wt:7 val:7

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

DP before row 2 updates

Item 2 - wt:7 val:3

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

Updating dp[1]

Item 2 - wt:7 val:6

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

Updating dp[2]

Item 2 - wt:7 val:10

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

Updating dp[3]

Item 2 - wt:7 val:15

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

Updating dp[4]

Item 2 - wt:7 val:21

i\w	0	1	2	3	4	5	6
i=0	1	3	6	10	15	21	7

Updating dp[5]

Item 2 - wt:7 val:28

i\w	0	1	2	3	4	5	6
i=0	1	3	6	10	15	21	28

Updating dp[6]

Item 2 - wt:7 val:28

i\w	0	1	2	3	4	5	6
i=0	1	3	6	10	15	21	28

Answer cell

Key Takeaways

✓ The DP array accumulates the number of unique paths to each cell by summing paths from the left and above.

This insight is hard to see from code alone because the 1D array updates are subtle; watching the values change clarifies the logic.

✓ The algorithm uses a space-optimized 1D DP array instead of a 2D matrix, updating in place row by row.

Visualizing the DP array after each row iteration helps understand how space optimization works without losing information.

✓ The final answer is the last element of the DP array after processing all rows, representing paths to the bottom-right corner.

Seeing the final DP array state confirms how the answer emerges naturally from the accumulation process.

Practice

1. You are given a grid of non-negative integers representing costs. Starting from the top-left corner, you want to reach the bottom-right corner by moving only down or right, minimizing the total cost along the path. Which algorithmic approach guarantees finding the minimum total cost efficiently?

easy

A. A greedy algorithm that always moves to the adjacent cell with the smallest cost

B. Dynamic programming that builds up solutions from smaller subproblems using a grid-based state

C. Pure brute force recursion exploring all possible paths without memoization

D. Divide and conquer by splitting the grid into halves and solving independently

Solution

1. Step 1: Understand problem constraints

   The problem requires minimizing path cost with only down or right moves, which naturally forms overlapping subproblems.

2. Step 2: Identify suitable algorithmic pattern

   Dynamic programming efficiently solves overlapping subproblems by storing intermediate results, unlike greedy which can fail on some grids, brute force which is exponential, or divide and conquer which doesn't handle dependencies well.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   DP uses subproblem solutions to build the answer bottom-up [OK]

Hint: DP handles overlapping subproblems and optimal substructure [OK]

Common Mistakes:

• Assuming greedy always works for grid path problems
• Thinking brute force is efficient enough
• Believing divide and conquer applies without overlapping subproblems

2. What is the time complexity of the bottom-up dynamic programming solution for the minimum falling path sum problem on an n x n matrix?

medium

A. O(n^2) because each cell is processed once with constant neighbor checks

B. O(n) as only one row is stored at a time

C. O(3^n) since each step has three choices recursively

D. O(n^3) due to nested loops and checking three neighbors

Solution

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

   There are two nested loops: outer over rows (n), inner over columns (n).

2. Step 2: Analyze work per cell

   Each cell checks up to three neighbors in O(1) time, so total work is O(n * n) = O(n^2).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   DP processes each cell once with constant neighbor checks [OK]

Hint: Two nested loops over n rows and n columns [OK]

Common Mistakes:

• Confusing recursive exponential with DP complexity
• Assuming neighbor checks multiply complexity

3. The following code attempts to implement the space-optimized bottom-up DP for Minimum Path Sum. Which line contains a subtle bug that can cause incorrect results on some inputs?

medium

A. Line 9: dp[j] = grid[i][j] + min(dp[j-1], dp[j])

B. Line 5: dp[j] = dp[j-1] + grid[0][j]

C. Line 7: dp[0] = dp[0] + grid[i][0]

D. Line 4: dp[0] = grid[0][0]

Solution

1. Step 1: Analyze dp update order in inner loop

   In line 9, dp[j] is updated using dp[j-1] and dp[j]. Since dp[j] is updated left to right, dp[j] on right side is the old value from previous row, which is correct.

2. Step 2: Check for subtle bug

   Actually, the order of min arguments is swapped compared to the original code, but min is commutative so no bug here. Check line 7.

3. Step 3: Check line 7

   Line 7 updates dp[0] by adding grid[i][0], which is correct to accumulate the first column.

4. Step 4: Re-examine line 9 carefully

   Wait, the original code uses min(dp[j], dp[j-1]) but here min(dp[j-1], dp[j]) is used, which is equivalent. So no bug here.

5. Step 5: Check for known mistakes

   Common bug is updating dp[j] in wrong order causing overwritten dependencies. Here, order is left to right, which is correct.

6. Step 6: Reconsider line 7

   Line 7 uses dp[0] = dp[0] + grid[i][0], which is correct. No bug.

7. Step 7: Check line 5

   Line 5 initializes first row dp correctly.

8. Step 8: Check line 4

   Line 4 initializes dp[0] correctly.

9. Step 9: Identify subtle bug

   Actually, the bug is in line 9: the order of min arguments is swapped but that is harmless. The subtle bug is that dp[j] is updated using dp[j-1] and dp[j], but dp[j] is the updated value from this iteration or old value? Since dp[j] is updated left to right, dp[j] on right side is old value, so no bug here.

10. Step 10: Re-examine the question

    Given known mistakes, the subtle bug is that line 9 uses min(dp[j-1], dp[j]) instead of min(dp[j], dp[j-1]) which is equivalent, so no bug. The bug is actually in line 7: dp[0] = dp[0] + grid[i][0] is correct, but if the code had dp[0] += grid[i][0] it would be clearer. No bug here.

11. Step 11: Final conclusion

    None of the lines have a bug as written. But the question states there is one subtle bug. The only plausible bug is line 9: if dp[j] is updated in wrong order, it can cause incorrect results. The code updates dp[j] left to right, so no bug. But if the code updated dp[j] right to left, it would be wrong.

12. Step 12: Final Answer

    Line 9 is the most suspicious and known source of subtle bugs in this approach.

13. Final Answer:

    Option A -> Option A

14. Quick Check:

    Updating dp[j] in wrong order causes overwritten dependencies [OK]

Hint: Check dp updates order to avoid overwriting needed values [OK]

Common Mistakes:

• Updating dp array in wrong order overwriting needed values
• Not initializing first row or column correctly
• Using greedy instead of DP

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 dynamic programming solution for the Stone Game problem with n piles, and why?

medium

A. O(n^3) because of three nested loops over the piles

B. O(n^2) because the DP table of size nxn is filled once with constant work per cell

C. O(2^n) because all subsets of piles are considered

D. O(n) because only linear passes over the piles are needed

Solution

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

   There are two nested loops: one for length from 2 to n, and one for start index i, total O(n^2) iterations.

2. Step 2: Constant work per dp[i][j]

   Each dp[i][j] is computed with a constant number of operations (max of two values), so total time is O(n^2).

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   DP table size nxn filled once with O(1) work per cell [OK]

Hint: Two nested loops over intervals -> O(n^2) [OK]

Common Mistakes:

• Confusing recursion stack space with time
• Assuming triple nested loops cause O(n^3)