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

2. You are given a triangular array of numbers where each element can only move to one of the two adjacent numbers in the row below. The goal is to find the minimum sum path from the top to the bottom. Which algorithmic approach guarantees an optimal solution efficiently?

easy

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

B. Divide and conquer by splitting the triangle into two halves and solving independently

C. Pure brute force recursion exploring all paths without memoization

D. Dynamic Programming using bottom-up tabulation to build minimum path sums

Solution

1. Step 1: Understand problem constraints and properties

   The problem requires finding a minimum path sum with overlapping subproblems and optimal substructure, which suits dynamic programming.

2. Step 2: Identify suitable algorithm

   Bottom-up DP tabulation efficiently computes minimum sums from the bottom row up, avoiding recomputation and ensuring optimality.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   DP tabulation solves overlapping subproblems efficiently [OK]

Hint: DP bottom-up tabulation ensures optimal substructure [OK]

Common Mistakes:

• Assuming greedy choice is always optimal
• Using brute force recursion without memoization
• Trying to split triangle independently ignoring dependencies

3. What is the time complexity of the bottom-up DP solution for the Cherry Pickup problem on an n x n grid, where dp is a 3D array indexed by step and two row positions of the players?

medium

A. O(4^n) due to exploring all possible paths for two players

B. O(n^3) because there are O(n) steps and O(n^2) states for the two players' rows, each computed in constant time

C. O(n^4) since for each dp state, four previous states are checked

D. O(n^2) as the dp only tracks positions of two players without step dimension

Solution

1. Step 1: Identify number of states

   There are 2n-1 steps, and for each step, possible row positions for player 1 and player 2 are each O(n), so total states are O(n^3).

2. Step 2: Analyze transitions per state

   Each dp state checks up to 4 previous states in O(1) time, so total time is O(n^3).

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   3D dp with O(n^3) states and constant transitions [OK]

Hint: Count states x transitions carefully [OK]

Common Mistakes:

• Confusing number of states with number of transitions
• Assuming exponential time due to recursion
• Ignoring that step dimension limits valid states

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

5. Suppose the problem is modified so that you can reuse the same color for adjacent houses, but you want to minimize the total cost. Which modification to the DP solution is correct?

hard

A. Use brute force recursion without memoization since constraints are relaxed.

B. Keep excluding the previous color but add a penalty cost for same color adjacency.

C. Remove the condition excluding the previous color when computing min_prev; just take min(dp) for all colors.

D. Use a greedy approach picking the cheapest color for each house independently.

Solution

1. Step 1: Understand constraint relaxation

   Allowing same color for adjacent houses removes the need to exclude previous color in DP transitions.

2. Step 2: Modify DP accordingly

   Now min_prev is simply min(dp) over all colors, no exclusion needed. This simplifies the DP and still finds minimum cost.

3. Step 3: Evaluate other options

   Adding penalty is unnecessary. Brute force is inefficient. Greedy fails because costs vary per house and color.

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   Relaxed constraints allow including all colors in min calculation [OK]

Hint: Relaxed constraints mean no exclusion of previous color in DP [OK]

Common Mistakes:

• Still excluding previous color unnecessarily
• Adding penalty complicates solution
• Using brute force or greedy incorrectly