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

3. What is the time complexity of the bottom-up dynamic programming solution for the Burst Balloons problem with input size n, and why?

medium

A. O(n^3) because for each interval we try all possible last balloons to burst

B. O(n^3) due to three nested loops iterating over intervals and burst positions

C. O(2^n) because of the exponential number of burst orders

D. O(n^2) because we fill a 2D dp table of size n by n

Solution

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

   There are three nested loops: length of interval (up to n), start index i (up to n), and position k (up to n) inside the interval.

2. Step 2: Calculate complexity

   Each loop runs up to n times, so total time is O(n * n * n) = O(n^3). The dp table is size O(n^2), but filling it requires the third loop over k.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Three nested loops over n -> O(n^3) time complexity [OK]

Hint: Three nested loops over intervals and positions cause cubic time [OK]

Common Mistakes:

• Confusing dp table size with time complexity
• Ignoring the innermost loop over k
• Assuming exponential time for DP solution

4. Suppose the Cherry Pickup problem is modified so that players can revisit cells multiple times (i.e., cycles allowed), and cherries are replenished after being picked (can be collected multiple times). Which of the following algorithmic changes correctly adapts the solution to this variant?

hard

A. Use the same 3D DP with memoization but remove the check that prevents revisiting cells.

B. Apply a greedy approach that always moves players to the next cell with the highest cherry count.

C. Use a 4D DP tracking both players' full positions and number of visits per cell to avoid double counting.

D. Switch to a shortest path algorithm like Dijkstra on a state graph representing both players' positions and steps, allowing cycles.

Solution

1. Step 1: Understand the impact of allowing revisits and replenished cherries

   Cycles and replenished cherries mean the problem is no longer acyclic and DP assumptions break down.

2. Step 2: Identify suitable algorithm

   Modeling the problem as a shortest path on a state graph with both players' positions and steps allows handling cycles and repeated cherry collection correctly.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   DP fails with cycles; shortest path algorithms handle repeated states [OK]

Hint: Cycles break DP; use graph shortest path [OK]

Common Mistakes:

• Removing DP constraints without changing algorithm
• Adding dimensions to DP without handling cycles
• Using greedy which ignores global optimality

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