Unique Paths

🎯

Unique Paths

mediumDPAmazonGoogleMicrosoft

Imagine a robot starting at the top-left corner of a grid, trying to reach the bottom-right corner by only moving right or down. How many unique ways can it reach the destination?

💡 This problem is a classic example of counting paths in a grid using dynamic programming. Beginners often struggle because the number of paths grows exponentially if approached naively, and they miss the overlapping subproblems that DP exploits.

📋

Problem Statement

Given two integers m and n representing the number of rows and columns of a grid, return the number of unique paths from the top-left corner (0,0) to the bottom-right corner (m-1,n-1). You can only move either down or right at any point in time.

1 ≤ m, n ≤ 100The answer is guaranteed to fit in a 32-bit integer.

💡

Example

Input"m = 3, n = 7"

Output28

There are 28 unique paths from top-left to bottom-right moving only right or down.

Input"m = 3, n = 2"

Output3

Paths: Right->Down->Down, Down->Right->Down, Down->Down->Right.

• m = 1, n = 1 → 1 (only one cell, start is end)
• m = 1, n = 10 → 1 (only one row, only one path moving right)
• m = 10, n = 1 → 1 (only one column, only one path moving down)
• m = 2, n = 2 → 2 (two paths: right->down or down->right)

🔁

Why DP?

Why greedy fails:

A greedy approach might try to always move right or always move down first, but this misses many valid paths. For example, in a 3x3 grid, always moving right first leads to only one path, missing others that mix moves.

DP state:

dp[i][j] represents the number of unique paths to reach cell (i, j) from the start (0,0).

Recurrence:dp[i][j] = dp[i-1][j] + dp[i][j-1]

The number of ways to get to cell (i,j) is the sum of ways to get to the cell above it and the cell to the left of it.

⚠️

Common Mistakes

Not handling base cases correctly

Incorrect path counts or index errors

✅ Initialize first row and column with 1s in DP or handle base cases in recursion

Recomputing subproblems in recursion without memoization

Time limit exceeded due to exponential calls

✅ Add memoization cache to store intermediate results

Off-by-one errors in indexing

Array index out of bounds or wrong results

✅ Carefully check loop ranges and base conditions

Using 2D DP when 1D DP suffices

Unnecessary space usage

✅ Optimize space by using a single array updated in place

Trying greedy approach

Incorrect path counts as greedy misses many paths

✅ Use DP to consider all possible paths

🧠

Brute Force (Pure Recursion)

💡 Starting with brute force helps understand the problem's recursive nature and why naive solutions are inefficient due to repeated calculations.

Intuition

Count paths by recursively moving right or down until reaching the bottom-right cell, summing all valid paths.

Algorithm

1. Start at cell (0,0).
2. If at bottom-right cell, return 1 as a valid path.
3. Otherwise, recursively count paths by moving right and down if within bounds.
4. Sum the counts from right and down moves and return.

💡 The recursion tree grows exponentially because each cell branches into two moves, making it hard to track without memoization.

Recurrence:uniquePaths(i,j) = uniquePaths(i+1,j) + uniquePaths(i,j+1)

</>

Code

def uniquePaths(m, n):
    def dfs(i, j):
        if i == m - 1 and j == n - 1:
            return 1
        if i >= m or j >= n:
            return 0
        return dfs(i + 1, j) + dfs(i, j + 1)

    return dfs(0, 0)

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

Line Notes

def dfs(i, j):Defines the recursive helper to count paths from cell (i,j).

if i == m - 1 and j == n - 1:Base case: reached destination, count as 1 path.

if i >= m or j >= n:Out of grid bounds, no valid path here.

return dfs(i + 1, j) + dfs(i, j + 1)Sum paths by moving down and right recursively.

public class UniquePaths {
    public static int uniquePaths(int m, int n) {
        return dfs(0, 0, m, n);
    }

    private static int dfs(int i, int j, int m, int n) {
        if (i == m - 1 && j == n - 1) return 1;
        if (i >= m || j >= n) return 0;
        return dfs(i + 1, j, m, n) + dfs(i, j + 1, m, n);
    }

    public static void main(String[] args) {
        System.out.println(uniquePaths(3, 7)); // Output: 28
    }
}

Line Notes

public static int uniquePaths(int m, int n)Entry method to start recursion from (0,0).

if (i == m - 1 && j == n - 1) return 1;Base case: reached destination cell.

if (i >= m || j >= n) return 0;Out of bounds, no path.

return dfs(i + 1, j, m, n) + dfs(i, j + 1, m, n);Sum paths from down and right moves.

#include <iostream>
using namespace std;

int dfs(int i, int j, int m, int n) {
    if (i == m - 1 && j == n - 1) return 1;
    if (i >= m || j >= n) return 0;
    return dfs(i + 1, j, m, n) + dfs(i, j + 1, m, n);
}

int uniquePaths(int m, int n) {
    return dfs(0, 0, m, n);
}

int main() {
    cout << uniquePaths(3, 7) << endl; // Output: 28
    return 0;
}

Line Notes

int dfs(int i, int j, int m, int n)Recursive helper counting paths from (i,j).

if (i == m - 1 && j == n - 1) return 1;Reached destination, count 1 path.

if (i >= m || j >= n) return 0;Out of grid bounds, no path.

return dfs(i + 1, j, m, n) + dfs(i, j + 1, m, n);Sum paths from down and right.

function uniquePaths(m, n) {
    function dfs(i, j) {
        if (i === m - 1 && j === n - 1) return 1;
        if (i >= m || j >= n) return 0;
        return dfs(i + 1, j) + dfs(i, j + 1);
    }
    return dfs(0, 0);
}

console.log(uniquePaths(3, 7)); // Output: 28

Line Notes

function dfs(i, j)Recursive function to count paths from (i,j).

if (i === m - 1 && j === n - 1) return 1;Base case: reached bottom-right cell.

if (i >= m || j >= n) return 0;Out of bounds, no path.

return dfs(i + 1, j) + dfs(i, j + 1);Sum paths from down and right moves.

⏱

Complexity

TimeO(2^(m+n))

SpaceO(m+n) due to recursion stack

Each cell branches into two recursive calls, leading to exponential growth in calls.

💡 For m=n=10, this means over a million calls, which is impractical.

Interview Verdict: TLE

This approach is too slow for large inputs but is essential to understand the problem's recursive structure.

🧠

Top-Down DP with Memoization

💡 Memoization avoids recomputing the same subproblems by caching results, drastically improving efficiency.

Intuition

Store the number of paths from each cell once computed, so repeated calls return cached results instead of recalculating.

Algorithm

1. Initialize a 2D cache array to store results for each cell.
2. Start recursion from (0,0).
3. If result for current cell is cached, return it.
4. Otherwise, compute paths by summing down and right moves recursively.
5. Cache and return the computed result.

💡 Memoization transforms exponential recursion into polynomial time by avoiding duplicate work.

Recurrence:dp[i][j] = dp[i+1][j] + dp[i][j+1]

</>

Code

def uniquePaths(m, n):
    memo = [[-1] * n for _ in range(m)]

    def dfs(i, j):
        if i == m - 1 and j == n - 1:
            return 1
        if i >= m or j >= n:
            return 0
        if memo[i][j] != -1:
            return memo[i][j]
        memo[i][j] = dfs(i + 1, j) + dfs(i, j + 1)
        return memo[i][j]

    return dfs(0, 0)

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

Line Notes

memo = [[-1] * n for _ in range(m)]Initialize cache with -1 indicating uncomputed cells.

if memo[i][j] != -1:Return cached result if available to avoid recomputation.

memo[i][j] = dfs(i + 1, j) + dfs(i, j + 1)Store computed paths count for current cell.

return memo[i][j]Return cached or newly computed result.

public class UniquePaths {
    public static int uniquePaths(int m, int n) {
        int[][] memo = new int[m][n];
        for (int i = 0; i < m; i++)
            Arrays.fill(memo[i], -1);
        return dfs(0, 0, m, n, memo);
    }

    private static int dfs(int i, int j, int m, int n, int[][] memo) {
        if (i == m - 1 && j == n - 1) return 1;
        if (i >= m || j >= n) return 0;
        if (memo[i][j] != -1) return memo[i][j];
        memo[i][j] = dfs(i + 1, j, m, n, memo) + dfs(i, j + 1, m, n, memo);
        return memo[i][j];
    }

    public static void main(String[] args) {
        System.out.println(uniquePaths(3, 7)); // Output: 28
    }
}

Line Notes

int[][] memo = new int[m][n];Create 2D cache array for memoization.

Arrays.fill(memo[i], -1);Mark all cells as uncomputed initially.

if (memo[i][j] != -1) return memo[i][j];Return cached result if available.

memo[i][j] = dfs(i + 1, j, m, n, memo) + dfs(i, j + 1, m, n, memo);Cache computed paths count.

#include <iostream>
#include <vector>
using namespace std;

int dfs(int i, int j, int m, int n, vector<vector<int>>& memo) {
    if (i == m - 1 && j == n - 1) return 1;
    if (i >= m || j >= n) return 0;
    if (memo[i][j] != -1) return memo[i][j];
    memo[i][j] = dfs(i + 1, j, m, n, memo) + dfs(i, j + 1, m, n, memo);
    return memo[i][j];
}

int uniquePaths(int m, int n) {
    vector<vector<int>> memo(m, vector<int>(n, -1));
    return dfs(0, 0, m, n, memo);
}

int main() {
    cout << uniquePaths(3, 7) << endl; // Output: 28
    return 0;
}

Line Notes

vector<vector<int>> memo(m, vector<int>(n, -1));Initialize memo table with -1 for uncomputed cells.

if (memo[i][j] != -1) return memo[i][j];Return cached result to avoid recomputation.

memo[i][j] = dfs(i + 1, j, m, n, memo) + dfs(i, j + 1, m, n, memo);Store computed number of paths.

return memo[i][j];Return memoized result.

function uniquePaths(m, n) {
    const memo = Array.from({ length: m }, () => Array(n).fill(-1));

    function dfs(i, j) {
        if (i === m - 1 && j === n - 1) return 1;
        if (i >= m || j >= n) return 0;
        if (memo[i][j] !== -1) return memo[i][j];
        memo[i][j] = dfs(i + 1, j) + dfs(i, j + 1);
        return memo[i][j];
    }

    return dfs(0, 0);
}

console.log(uniquePaths(3, 7)); // Output: 28

Line Notes

const memo = Array.from({ length: m }, () => Array(n).fill(-1));Create 2D memo array initialized to -1.

if (memo[i][j] !== -1) return memo[i][j];Return cached value if computed.

memo[i][j] = dfs(i + 1, j) + dfs(i, j + 1);Cache the sum of paths from down and right.

return memo[i][j];Return memoized result.

⏱

Complexity

TimeO(m*n)

SpaceO(m*n) for memo table and recursion stack

Each cell is computed once and cached, reducing exponential calls to polynomial.

💡 For m=n=10, about 100 computations instead of millions.

Interview Verdict: Accepted

Memoization makes the solution efficient and practical for interview constraints.

🧠

Bottom-Up DP (Tabulation)

💡 Tabulation builds the solution iteratively from the base case, often easier to understand and less error-prone than recursion.

Intuition

Start from the top-left cell and fill a dp table row by row, where each cell's value is the sum of the cell above and to the left.

Algorithm

1. Initialize a 2D dp array with 1s in the first row and first column (only one path to those cells).
2. Iterate over the grid starting from cell (1,1).
3. For each cell, set dp[i][j] = dp[i-1][j] + dp[i][j-1].
4. Return dp[m-1][n-1] as the total unique paths.

💡 This approach uses the problem's optimal substructure and overlapping subproblems explicitly in a bottom-up manner.

Recurrence:dp[i][j] = dp[i-1][j] + dp[i][j-1]

</>

Code

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

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

Line Notes

dp = [[1] * n for _ in range(m)]Initialize dp with 1s for first row and column (only one path).

for i in range(1, m):Iterate rows starting from second row.

for j in range(1, n):Iterate columns starting from second column.

dp[i][j] = dp[i - 1][j] + dp[i][j - 1]Sum paths from top and left neighbors.

public class UniquePaths {
    public static int uniquePaths(int m, int n) {
        int[][] dp = new int[m][n];
        for (int i = 0; i < m; i++) dp[i][0] = 1;
        for (int j = 0; j < n; j++) dp[0][j] = 1;
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }
        return dp[m - 1][n - 1];
    }

    public static void main(String[] args) {
        System.out.println(uniquePaths(3, 7)); // Output: 28
    }
}

Line Notes

int[][] dp = new int[m][n];Create dp table to store path counts.

dp[i][0] = 1;Only one way to reach cells in first column (down moves).

dp[0][j] = 1;Only one way to reach cells in first row (right moves).

dp[i][j] = dp[i - 1][j] + dp[i][j - 1];Sum paths from top and left neighbors.

#include <iostream>
#include <vector>
using namespace std;

int uniquePaths(int m, int n) {
    vector<vector<int>> dp(m, vector<int>(n, 1));
    for (int i = 1; i < m; i++) {
        for (int j = 1; j < n; j++) {
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
        }
    }
    return dp[m - 1][n - 1];
}

int main() {
    cout << uniquePaths(3, 7) << endl; // Output: 28
    return 0;
}

Line Notes

vector<vector<int>> dp(m, vector<int>(n, 1));Initialize dp with 1s for first row and column.

for (int i = 1; i < m; i++)Iterate rows from second row.

for (int j = 1; j < n; j++)Iterate columns from second column.

dp[i][j] = dp[i - 1][j] + dp[i][j - 1];Sum paths from top and left cells.

function uniquePaths(m, n) {
    const dp = Array.from({ length: m }, () => Array(n).fill(1));
    for (let i = 1; i < m; i++) {
        for (let j = 1; j < n; j++) {
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
        }
    }
    return dp[m - 1][n - 1];
}

console.log(uniquePaths(3, 7)); // Output: 28

Line Notes

const dp = Array.from({ length: m }, () => Array(n).fill(1));Initialize dp with 1s for first row and column.

for (let i = 1; i < m; i++)Loop over rows starting from second row.

for (let j = 1; j < n; j++)Loop over columns starting from second column.

dp[i][j] = dp[i - 1][j] + dp[i][j - 1];Sum paths from above and left cells.

⏱

Complexity

TimeO(m*n)

SpaceO(m*n)

We fill each cell once, computing the sum of two neighbors.

💡 For m=n=10, about 100 operations, very efficient.

Interview Verdict: Accepted

This is the standard DP solution for this problem, optimal in time and straightforward to implement.

🧠

Space Optimized Bottom-Up DP

💡 Since dp[i][j] depends only on the current row and previous row, we can reduce space to O(n) by using a single array.

Intuition

Use a 1D array to store path counts for the current row, updating it as we move through columns.

Algorithm

1. Initialize a 1D dp array of size n with all 1s (first row).
2. Iterate over rows from the second row to the last.
3. For each column from 1 to n-1, update dp[j] = dp[j] + dp[j-1].
4. Return dp[n-1] as the total unique paths.

💡 This approach reuses the dp array to accumulate path counts, saving space without losing correctness.

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

</>

Code

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]

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

Line Notes

dp = [1] * nInitialize dp array with 1s representing first row paths.

for i in range(1, m):Iterate over rows starting from second row.

for j in range(1, n):Iterate columns from second column.

dp[j] += dp[j - 1]Update current cell paths by adding left neighbor's paths.

public class UniquePaths {
    public static int uniquePaths(int m, int n) {
        int[] dp = new int[n];
        Arrays.fill(dp, 1);
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[j] += dp[j - 1];
            }
        }
        return dp[n - 1];
    }

    public static void main(String[] args) {
        System.out.println(uniquePaths(3, 7)); // Output: 28
    }
}

Line Notes

int[] dp = new int[n];Create 1D dp array for current row path counts.

Arrays.fill(dp, 1);Initialize first row with 1s.

for (int j = 1; j < n; j++)Iterate columns from second column.

dp[j] += dp[j - 1];Add paths from left cell to current cell.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int uniquePaths(int m, int n) {
    vector<int> dp(n, 1);
    for (int i = 1; i < m; i++) {
        for (int j = 1; j < n; j++) {
            dp[j] += dp[j - 1];
        }
    }
    return dp[n - 1];
}

int main() {
    cout << uniquePaths(3, 7) << endl; // Output: 28
    return 0;
}

Line Notes

vector<int> dp(n, 1);Initialize 1D dp array with 1s for first row.

for (int i = 1; i < m; i++)Iterate over rows starting from second.

for (int j = 1; j < n; j++)Iterate columns from second column.

dp[j] += dp[j - 1];Update dp[j] by adding left neighbor's paths.

function uniquePaths(m, n) {
    const dp = new Array(n).fill(1);
    for (let i = 1; i < m; i++) {
        for (let j = 1; j < n; j++) {
            dp[j] += dp[j - 1];
        }
    }
    return dp[n - 1];
}

console.log(uniquePaths(3, 7)); // Output: 28

Line Notes

const dp = new Array(n).fill(1);Initialize dp array with 1s for first row.

for (let i = 1; i < m; i++)Loop over rows starting from second.

for (let j = 1; j < n; j++)Loop over columns from second column.

dp[j] += dp[j - 1];Add left neighbor's paths to current cell.

⏱

Complexity

TimeO(m*n)

SpaceO(n)

We only keep one row of dp, updating it in place.

💡 For m=n=10, only 10 space used instead of 100.

Interview Verdict: Accepted

This is the most space-efficient DP solution, ideal for large grids.

📊

All Approaches - One-Glance Tradeoffs

💡 In interviews, coding the bottom-up DP or space-optimized DP is usually best; mention brute force and memoization to show understanding.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(2^(m+n))	O(m+n) recursion stack	Yes (deep recursion)	N/A	Mention only - never code
2. Top-Down DP with Memoization	O(m*n)	O(m*n)	Possible but unlikely for constraints	Yes	Good to mention and code if comfortable
3. Bottom-Up DP (Tabulation)	O(m*n)	O(m*n)	No	Yes	Best approach to code in most interviews
4. Space Optimized Bottom-Up DP	O(m*n)	O(n)	No	Yes, with extra bookkeeping	Mention as optimization after coding 2D DP

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice coding all approaches, and prepare to explain tradeoffs clearly in interviews.

How to Present

Step 1: Clarify problem constraints and movement rules.Step 2: Describe brute force recursion to show problem structure.Step 3: Introduce memoization to optimize overlapping subproblems.Step 4: Present bottom-up DP for clarity and efficiency.Step 5: Mention space optimization as an advanced improvement.

Time Allocation

Clarify: 2min → Approach: 3min → Code: 10min → Test & Optimize: 5min. Total ~20min

What the Interviewer Tests

Understanding of recursion, dynamic programming concepts, ability to optimize naive solutions, and code correctness.

Common Follow-ups

• How to handle obstacles in the grid? → Modify DP to skip blocked cells.
• Can you compute the number of paths using combinatorics? → Use binomial coefficients.

💡 These follow-ups test adaptability and knowledge of alternative solutions.

🔍

Pattern Recognition

When to Use

1) Counting paths or ways in a grid; 2) Movement restricted to right/down; 3) Overlapping subproblems visible; 4) Optimal substructure present.

Signature Phrases

'number of unique paths''only move right or down''from top-left to bottom-right'

NOT This Pattern When

Problems involving arbitrary moves or no overlapping subproblems are not this pattern.

Similar Problems

Unique Paths II - adds obstacles, similar DP with blocked cellsMinimum Path Sum - similar grid DP but minimizing costNumber of Distinct Islands - counting shapes, related grid traversal

Practice

1. You are given an n x n integer matrix. You want to find a path from the top row to the bottom row such that you move one step down each time, and at each step you can move to the same column, the column to the left, or the column to the right. The goal is to minimize the sum of the values along this path. Which algorithmic approach guarantees finding the minimum sum efficiently?

easy

A. Greedy algorithm that picks the minimum adjacent value at each step

B. Sorting each row and picking the smallest values independently

C. Depth-first search exploring all paths without memoization

D. Dynamic programming that builds solutions row by row using previous row results

Solution

1. Step 1: Understand the problem constraints

   The problem requires considering all possible paths moving down and diagonally, which suggests overlapping subproblems and optimal substructure.

2. Step 2: Identify the suitable algorithm

   Dynamic programming fits because it efficiently computes minimum sums for each cell based on the previous row's results, avoiding redundant calculations.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Greedy and sorting fail to consider future steps; DFS without memoization is exponential [OK]

Hint: DP uses previous row results to build solutions [OK]

Common Mistakes:

• Thinking greedy or sorting per row suffices
• Ignoring overlapping subproblems

2. Consider the following Python function implementing the minimum falling path sum using bottom-up DP:

def minFallingPathSum(matrix):
    n = len(matrix)
    dp = matrix[0][:]

    for i in range(1, n):
        new_dp = [0]*n
        for j in range(n):
            best = dp[j]
            if j > 0:
                best = min(best, dp[j-1])
            if j < n - 1:
                best = min(best, dp[j+1])
            new_dp[j] = matrix[i][j] + best
        dp = new_dp

    return min(dp)

matrix = [[2,1,3],[6,5,4],[7,8,9]]
print(minFallingPathSum(matrix))

What is the output of this code?

easy

A. 12

B. 13

C. 14

D. 15

Solution

1. Step 1: Trace dp after first row

   dp = [2, 1, 3]

2. Step 2: Compute dp for second row

   For i=1: - j=0: best = min(dp[0], dp[1]) = min(2,1) = 1 -> new_dp[0] = 6 + 1 = 7 - j=1: best = min(dp[1], dp[0], dp[2]) = min(1,2,3) = 1 -> new_dp[1] = 5 + 1 = 6 - j=2: best = min(dp[2], dp[1]) = min(3,1) = 1 -> new_dp[2] = 4 + 1 = 5 So new_dp = [7, 6, 5]

3. Step 3: Compute dp for third row

   For i=2: - j=0: best = min(new_dp[0], new_dp[1]) = min(7,6) = 6 -> new_dp[0] = 7 + 6 = 13 - j=1: best = min(new_dp[1], new_dp[0], new_dp[2]) = min(6,7,5) = 5 -> new_dp[1] = 8 + 5 = 13 - j=2: best = min(new_dp[2], new_dp[1]) = min(5,6) = 5 -> new_dp[2] = 9 + 5 = 14 So new_dp = [13, 13, 14]

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Minimum of last dp row is 13 [OK]

Hint: Trace dp row by row, pick min at end [OK]

Common Mistakes:

• Off-by-one in indices
• Using old dp instead of new_dp values

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

4. You are given a printer that can print a continuous substring of identical characters in one turn. Given a string, you want to find the minimum number of turns needed to print the entire string. Which algorithmic approach guarantees an optimal solution for this problem?

easy

A. Dynamic Programming over intervals with string compression and merging states

B. Greedy approach printing each character separately from left to right

C. Simple recursion without memoization or compression

D. Sliding window technique to find longest repeated substrings

Solution

1. Step 1: Understand problem constraints

   The problem requires minimizing turns to print a string where each turn prints a continuous block of identical characters.

2. Step 2: Identify suitable algorithmic pattern

   Greedy or sliding window approaches fail to merge overlapping prints optimally. Pure recursion is inefficient. Interval DP with string compression and merging states captures overlapping subproblems and optimizes turns.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Interval DP with compression is known optimal [OK]

Hint: Interval DP with compression merges overlapping prints [OK]

Common Mistakes:

• Assuming greedy printing each char separately is optimal

5. Suppose the Zuma Game variant allows reusing balls from the hand infinitely many times (unlimited supply). Which modification to the algorithm is necessary to correctly compute the minimal insertions?

hard

A. Add a visited set to memoize only board states without hand counts

B. Keep hand_count but reset counts after each recursion to simulate reuse

C. Use greedy insertion since infinite supply guarantees minimal moves by earliest removal

D. Remove hand_count tracking and treat hand as infinite supply; use interval DP without hand state

Solution

1. Step 1: Understand infinite supply impact

   With unlimited balls, hand counts are irrelevant; only board intervals matter.

2. Step 2: Modify DP state and transitions

   Remove hand_count from state and transitions; interval DP can focus solely on board intervals to find minimal insertions.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Infinite supply simplifies state, removing hand count dimension [OK]

Hint: Infinite supply removes hand count dimension [OK]

Common Mistakes:

• Resetting hand counts incorrectly simulates reuse
• Using greedy approach which may not be minimal
• Memoizing without hand counts but missing board state uniqueness