Minimum Path Sum

🎯

Minimum Path Sum

mediumDPAmazonGoogleMicrosoft

Imagine you are navigating a grid-like city where each block has a cost to cross. You want to find the cheapest route from the top-left corner to the bottom-right corner, moving only right or down.

💡 This problem is a classic example of grid-based dynamic programming. Beginners often struggle because they try to solve it greedily or with brute force without recognizing overlapping subproblems and optimal substructure. Understanding how to build solutions incrementally using DP tables is key.

📋

Problem Statement

Given an m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path. You can only move either down or right at any point in time.

m == grid.lengthn == grid[i].length1 ≤ m, n ≤ 2000 ≤ grid[i][j] ≤ 100

💡

Example

Input"[[1,3,1],[1,5,1],[4,2,1]]"

Output7

The path 1→3→1→1→1 minimizes the sum.

• Single cell grid → output is the cell value
• Grid with all zeros → output is 0
• Grid with one row → sum of that row
• Grid with one column → sum of that column

🔁

Why DP?

Why greedy fails:

A greedy approach that always picks the minimum of the right or down cell at each step can fail. For example, in grid [[1,100,1],[1,1,1]], greedy picks right first (1→100), but the optimal path is down then right (1→1→1→1).

DP state:

dp[i][j] represents the minimum path sum to reach cell (i, j) from the top-left corner.

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

The minimum path sum to cell (i,j) is its own cost plus the minimum of the sums to the cell above or to the left.

⚠️

Common Mistakes

Not handling boundaries correctly when filling dp

Index out of range errors or incorrect sums

✅ Explicitly initialize first row and first column before filling rest of dp

Using greedy approach picking min neighbor at each step

Incorrect answer on some grids

✅ Use DP to consider all paths, not just local minimum

Not memoizing in top-down approach

Time limit exceeded due to exponential calls

✅ Add memo table to cache results

Updating dp array in wrong order in space optimized approach

Incorrect dp values due to overwritten dependencies

✅ Iterate columns left to right to preserve dependencies

Modifying input grid without copying when not allowed

Unexpected side effects or wrong answers if input reused

✅ Use separate dp array or clarify input mutability

🧠

Brute Force (Pure Recursion)

💡 Starting with brute force helps understand the problem's recursive structure and why naive recursion is inefficient due to repeated calculations.

Intuition

From each cell, recursively explore paths moving right and down, summing costs, and return the minimum sum path to the bottom-right.

Algorithm

1. Start at the top-left cell (0,0).
2. Recursively compute the minimum path sum for the cell to the right and the cell below.
3. Return the current cell's cost plus the minimum of these two recursive results.
4. Base case: when reaching the bottom-right cell, return its cost.

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

Recurrence:f(i,j) = grid[i][j] + min(f(i+1,j), f(i,j+1))

</>

Code

def minPathSum(grid):
    m, n = len(grid), len(grid[0])
    def dfs(i, j):
        if i == m - 1 and j == n - 1:
            return grid[i][j]
        if i >= m or j >= n:
            return float('inf')
        right = dfs(i, j + 1)
        down = dfs(i + 1, j)
        return grid[i][j] + min(right, down)

    return dfs(0, 0)

# Example usage
if __name__ == '__main__':
    grid = [[1,3,1],[1,5,1],[4,2,1]]
    print(minPathSum(grid))  # Output: 7

Line Notes

def dfs(i, j):Defines recursive helper to compute min path sum from (i,j)

if i == m - 1 and j == n - 1:Base case: reached bottom-right cell, return its cost

if i >= m or j >= n:Out of bounds, return infinity to ignore invalid paths

return grid[i][j] + min(right, down)Add current cell cost to minimum of right and down paths

public class Solution {
    public int minPathSum(int[][] grid) {
        return dfs(grid, 0, 0);
    }

    private int dfs(int[][] grid, int i, int j) {
        int m = grid.length, n = grid[0].length;
        if (i == m - 1 && j == n - 1) return grid[i][j];
        if (i >= m || j >= n) return Integer.MAX_VALUE;
        int right = dfs(grid, i, j + 1);
        int down = dfs(grid, i + 1, j);
        return grid[i][j] + Math.min(right, down);
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        int[][] grid = {{1,3,1},{1,5,1},{4,2,1}};
        System.out.println(sol.minPathSum(grid)); // 7
    }
}

Line Notes

public int minPathSum(int[][] grid)Entry point calling recursive dfs from (0,0)

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

if (i >= m || j >= n)Bounds check to avoid invalid indices

return grid[i][j] + Math.min(right, down)Add current cell cost to minimum of next steps

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

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        return dfs(grid, 0, 0);
    }

private:
    int dfs(vector<vector<int>>& grid, int i, int j) {
        int m = grid.size(), n = grid[0].size();
        if (i == m - 1 && j == n - 1) return grid[i][j];
        if (i >= m || j >= n) return INT_MAX;
        int right = dfs(grid, i, j + 1);
        int down = dfs(grid, i + 1, j);
        return grid[i][j] + min(right, down);
    }
};

int main() {
    Solution sol;
    vector<vector<int>> grid = {{1,3,1},{1,5,1},{4,2,1}};
    cout << sol.minPathSum(grid) << endl; // 7
    return 0;
}

Line Notes

int dfs(vector<vector<int>>& grid, int i, int j)Recursive helper to compute min path sum from (i,j)

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

if (i >= m || j >= n)Return max int to ignore invalid paths

return grid[i][j] + min(right, down)Add current cell cost to minimum of right and down

var minPathSum = function(grid) {
    const m = grid.length, n = grid[0].length;
    function dfs(i, j) {
        if (i === m - 1 && j === n - 1) return grid[i][j];
        if (i >= m || j >= n) return Infinity;
        const right = dfs(i, j + 1);
        const down = dfs(i + 1, j);
        return grid[i][j] + Math.min(right, down);
    }
    return dfs(0, 0);
};

// Example usage
console.log(minPathSum([[1,3,1],[1,5,1],[4,2,1]])); // 7

Line Notes

function dfs(i, j)Recursive function to find min path sum from (i,j)

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

if (i >= m || j >= n)Return Infinity to discard invalid paths

return grid[i][j] + Math.min(right, down)Add current cell cost to minimum of next moves

⏱

Complexity

TimeO(2^(m+n))

SpaceO(m+n) due to recursion stack

Each cell branches into two recursive calls, leading to exponential time. The recursion stack depth is at most m+n.

💡 For a 3x3 grid, this means up to 2^6=64 calls, which grows quickly and becomes impractical for larger grids.

Interview Verdict: TLE

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

🧠

Top-Down Memoization

💡 Memoization caches results of recursive calls to avoid recomputation, drastically improving efficiency while preserving the recursive intuition.

Intuition

Use recursion as before but store results for each cell so repeated calls return cached answers instead of recomputing.

Algorithm

1. Initialize a memo table to store minimum path sums for each cell.
2. Recursively compute minimum path sums as before.
3. Before computing a cell, check if its result is already cached in memo.
4. Return cached result if available; otherwise compute, cache, and return.

💡 Memoization transforms exponential recursion into polynomial time by pruning duplicate calls.

Recurrence:f(i,j) = grid[i][j] + min(f(i+1,j), f(i,j+1)) with memoization

</>

Code

def minPathSum(grid):
    m, n = len(grid), len(grid[0])
    memo = [[-1]*n for _ in range(m)]
    def dfs(i, j):
        if i == m - 1 and j == n - 1:
            return grid[i][j]
        if i >= m or j >= n:
            return float('inf')
        if memo[i][j] != -1:
            return memo[i][j]
        right = dfs(i, j + 1)
        down = dfs(i + 1, j)
        memo[i][j] = grid[i][j] + min(right, down)
        return memo[i][j]

    return dfs(0, 0)

# Example usage
if __name__ == '__main__':
    grid = [[1,3,1],[1,5,1],[4,2,1]]
    print(minPathSum(grid))  # Output: 7

Line Notes

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

if memo[i][j] != -1:Return cached result if already computed

memo[i][j] = grid[i][j] + min(right, down)Store computed minimum path sum for reuse

return memo[i][j]Return memoized result to avoid recomputation

public class Solution {
    public int minPathSum(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        int[][] memo = new int[m][n];
        for (int[] row : memo) Arrays.fill(row, -1);
        return dfs(grid, 0, 0, memo);
    }

    private int dfs(int[][] grid, int i, int j, int[][] memo) {
        int m = grid.length, n = grid[0].length;
        if (i == m - 1 && j == n - 1) return grid[i][j];
        if (i >= m || j >= n) return Integer.MAX_VALUE;
        if (memo[i][j] != -1) return memo[i][j];
        int right = dfs(grid, i, j + 1, memo);
        int down = dfs(grid, i + 1, j, memo);
        memo[i][j] = grid[i][j] + Math.min(right, down);
        return memo[i][j];
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        int[][] grid = {{1,3,1},{1,5,1},{4,2,1}};
        System.out.println(sol.minPathSum(grid)); // 7
    }
}

Line Notes

int[][] memo = new int[m][n];Create memo table to cache results

for (int[] row : memo) Arrays.fill(row, -1);Initialize memo with -1 to mark unvisited cells

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

memo[i][j] = grid[i][j] + Math.min(right, down);Store computed minimum path sum

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

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        vector<vector<int>> memo(m, vector<int>(n, -1));
        return dfs(grid, 0, 0, memo);
    }

private:
    int dfs(vector<vector<int>>& grid, int i, int j, vector<vector<int>>& memo) {
        int m = grid.size(), n = grid[0].size();
        if (i == m - 1 && j == n - 1) return grid[i][j];
        if (i >= m || j >= n) return INT_MAX;
        if (memo[i][j] != -1) return memo[i][j];
        int right = dfs(grid, i, j + 1, memo);
        int down = dfs(grid, i + 1, j, memo);
        memo[i][j] = grid[i][j] + min(right, down);
        return memo[i][j];
    }
};

int main() {
    Solution sol;
    vector<vector<int>> grid = {{1,3,1},{1,5,1},{4,2,1}};
    cout << sol.minPathSum(grid) << endl; // 7
    return 0;
}

Line Notes

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

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

memo[i][j] = grid[i][j] + min(right, down);Store computed minimum path sum

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

var minPathSum = function(grid) {
    const m = grid.length, n = grid[0].length;
    const memo = Array.from({length: m}, () => Array(n).fill(-1));
    function dfs(i, j) {
        if (i === m - 1 && j === n - 1) return grid[i][j];
        if (i >= m || j >= n) return Infinity;
        if (memo[i][j] !== -1) return memo[i][j];
        const right = dfs(i, j + 1);
        const down = dfs(i + 1, j);
        memo[i][j] = grid[i][j] + Math.min(right, down);
        return memo[i][j];
    }
    return dfs(0, 0);
};

// Example usage
console.log(minPathSum([[1,3,1],[1,5,1],[4,2,1]])); // 7

Line Notes

const memo = Array.from({length: m}, () => Array(n).fill(-1));Create memo table initialized with -1

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

memo[i][j] = grid[i][j] + Math.min(right, down);Cache computed minimum path sum

return memo[i][j];Return memoized value

⏱

Complexity

TimeO(m*n)

SpaceO(m*n) for memo and recursion stack

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

💡 For a 200x200 grid, this means 40,000 computations, which is efficient and feasible.

Interview Verdict: Accepted

Memoization makes the solution efficient enough for interview constraints and is a common optimization step.

🧠

Bottom-Up Tabulation

💡 Tabulation builds the solution iteratively from the base case, avoiding recursion and making the flow easier to understand and debug.

Intuition

Create a dp table where each cell stores the minimum path sum to reach it, filling the table row by row from top-left to bottom-right.

Algorithm

1. Initialize a dp table of the same size as grid.
2. Set dp[0][0] to grid[0][0].
3. Fill the first row and first column by accumulating sums since only one path exists.
4. For each other cell, set dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1]).
5. Return dp[m-1][n-1] as the answer.

💡 This approach explicitly shows how each cell depends on its top and left neighbors, making dependencies clear.

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

</>

Code

def minPathSum(grid):
    m, n = len(grid), len(grid[0])
    dp = [[0]*n for _ in range(m)]
    dp[0][0] = grid[0][0]
    for i in range(1, m):
        dp[i][0] = dp[i-1][0] + grid[i][0]
    for j in range(1, n):
        dp[0][j] = dp[0][j-1] + grid[0][j]
    for i in range(1, m):
        for j in range(1, n):
            dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])
    return dp[m-1][n-1]

# Example usage
if __name__ == '__main__':
    grid = [[1,3,1],[1,5,1],[4,2,1]]
    print(minPathSum(grid))  # Output: 7

Line Notes

dp = [[0]*n for _ in range(m)]Create dp table to store minimum path sums

dp[0][0] = grid[0][0]Initialize starting cell with grid cost

dp[i][0] = dp[i-1][0] + grid[i][0]Fill first column by accumulating costs from above

dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])Fill dp cell using top and left neighbors

public class Solution {
    public int minPathSum(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        int[][] dp = new int[m][n];
        dp[0][0] = grid[0][0];
        for (int i = 1; i < m; i++) dp[i][0] = dp[i-1][0] + grid[i][0];
        for (int j = 1; j < n; j++) dp[0][j] = dp[0][j-1] + grid[0][j];
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[i][j] = grid[i][j] + Math.min(dp[i-1][j], dp[i][j-1]);
            }
        }
        return dp[m-1][n-1];
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        int[][] grid = {{1,3,1},{1,5,1},{4,2,1}};
        System.out.println(sol.minPathSum(grid)); // 7
    }
}

Line Notes

int[][] dp = new int[m][n];Create dp table for storing minimum sums

dp[0][0] = grid[0][0];Initialize starting point

dp[i][0] = dp[i-1][0] + grid[i][0];Fill first column cumulatively

dp[i][j] = grid[i][j] + Math.min(dp[i-1][j], dp[i][j-1]);Fill dp cell using top and left neighbors

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

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        vector<vector<int>> dp(m, vector<int>(n));
        dp[0][0] = grid[0][0];
        for (int i = 1; i < m; i++) dp[i][0] = dp[i-1][0] + grid[i][0];
        for (int j = 1; j < n; j++) dp[0][j] = dp[0][j-1] + grid[0][j];
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1]);
            }
        }
        return dp[m-1][n-1];
    }
};

int main() {
    Solution sol;
    vector<vector<int>> grid = {{1,3,1},{1,5,1},{4,2,1}};
    cout << sol.minPathSum(grid) << endl; // 7
    return 0;
}

Line Notes

vector<vector<int>> dp(m, vector<int>(n));Create dp table for minimum sums

dp[0][0] = grid[0][0];Initialize starting cell

dp[i][0] = dp[i-1][0] + grid[i][0];Fill first column cumulatively

dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1]);Fill dp cell using neighbors

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

// Example usage
console.log(minPathSum([[1,3,1],[1,5,1],[4,2,1]])); // 7

Line Notes

const dp = Array.from({length: m}, () => Array(n).fill(0));Create dp table initialized with zeros

dp[0][0] = grid[0][0];Initialize starting cell

dp[i][0] = dp[i-1][0] + grid[i][0];Fill first column cumulatively

dp[i][j] = grid[i][j] + Math.min(dp[i-1][j], dp[i][j-1]);Fill dp cell using top and left neighbors

⏱

Complexity

TimeO(m*n)

SpaceO(m*n)

We fill each cell once, and each cell computation takes O(1).

💡 For a 200x200 grid, this means 40,000 operations, which is efficient.

Interview Verdict: Accepted

Tabulation is often preferred for its clarity and iterative nature.

🧠

Space Optimized Bottom-Up

💡 Since dp[i][j] depends only on dp[i-1][j] (previous row) and dp[i][j-1] (current row), we can reduce space to one dimension.

Intuition

Use a single array to store minimum path sums for the current row, updating it as we move along columns.

Algorithm

1. Initialize a 1D dp array with size equal to number of columns.
2. Fill dp for the first row cumulatively.
3. For each subsequent row, update dp[0] by adding the current cell cost.
4. For each column j > 0, update dp[j] = grid[i][j] + min(dp[j], dp[j-1]).
5. Return dp[n-1] as the minimum path sum.

💡 This approach carefully updates dp in place, preserving needed values for the next computation.

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

</>

Code

def minPathSum(grid):
    m, n = len(grid), len(grid[0])
    dp = [0]*n
    dp[0] = grid[0][0]
    for j in range(1, n):
        dp[j] = dp[j-1] + grid[0][j]
    for i in range(1, m):
        dp[0] += grid[i][0]
        for j in range(1, n):
            dp[j] = grid[i][j] + min(dp[j], dp[j-1])
    return dp[-1]

# Example usage
if __name__ == '__main__':
    grid = [[1,3,1],[1,5,1],[4,2,1]]
    print(minPathSum(grid))  # Output: 7

Line Notes

dp = [0]*nInitialize 1D dp array for current row minimum sums

dp[0] = grid[0][0]Set starting cell cost

dp[j] = dp[j-1] + grid[0][j]Fill first row cumulatively

dp[j] = grid[i][j] + min(dp[j], dp[j-1])Update dp[j] using top (dp[j]) and left (dp[j-1]) values

public class Solution {
    public int minPathSum(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        int[] dp = new int[n];
        dp[0] = grid[0][0];
        for (int j = 1; j < n; j++) dp[j] = dp[j-1] + grid[0][j];
        for (int i = 1; i < m; i++) {
            dp[0] += grid[i][0];
            for (int j = 1; j < n; j++) {
                dp[j] = grid[i][j] + Math.min(dp[j], dp[j-1]);
            }
        }
        return dp[n-1];
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        int[][] grid = {{1,3,1},{1,5,1},{4,2,1}};
        System.out.println(sol.minPathSum(grid)); // 7
    }
}

Line Notes

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

dp[0] = grid[0][0];Initialize starting cell

dp[j] = dp[j-1] + grid[0][j];Fill first row cumulatively

dp[j] = grid[i][j] + Math.min(dp[j], dp[j-1]);Update dp[j] using previous row and left neighbor

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

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        vector<int> dp(n);
        dp[0] = grid[0][0];
        for (int j = 1; j < n; j++) dp[j] = dp[j-1] + grid[0][j];
        for (int i = 1; i < m; i++) {
            dp[0] += grid[i][0];
            for (int j = 1; j < n; j++) {
                dp[j] = grid[i][j] + min(dp[j], dp[j-1]);
            }
        }
        return dp[n-1];
    }
};

int main() {
    Solution sol;
    vector<vector<int>> grid = {{1,3,1},{1,5,1},{4,2,1}};
    cout << sol.minPathSum(grid) << endl; // 7
    return 0;
}

Line Notes

vector<int> dp(n);Create 1D dp vector for current row

dp[0] = grid[0][0];Initialize starting cell

dp[j] = dp[j-1] + grid[0][j];Fill first row cumulatively

dp[j] = grid[i][j] + min(dp[j], dp[j-1]);Update dp[j] using previous row and left neighbor

var minPathSum = function(grid) {
    const m = grid.length, n = grid[0].length;
    const dp = new Array(n).fill(0);
    dp[0] = grid[0][0];
    for (let j = 1; j < n; j++) dp[j] = dp[j-1] + grid[0][j];
    for (let i = 1; i < m; i++) {
        dp[0] += grid[i][0];
        for (let j = 1; j < n; j++) {
            dp[j] = grid[i][j] + Math.min(dp[j], dp[j-1]);
        }
    }
    return dp[n-1];
};

// Example usage
console.log(minPathSum([[1,3,1],[1,5,1],[4,2,1]])); // 7

Line Notes

const dp = new Array(n).fill(0);Initialize 1D dp array

dp[0] = grid[0][0];Set starting cell cost

dp[j] = dp[j-1] + grid[0][j];Fill first row cumulatively

dp[j] = grid[i][j] + Math.min(dp[j], dp[j-1]);Update dp[j] using top and left values

⏱

Complexity

TimeO(m*n)

SpaceO(n)

We use a single array of size n and update it for each row, reducing space from O(m*n) to O(n).

💡 For a 200x200 grid, this reduces memory usage from 40,000 ints to 200 ints.

Interview Verdict: Accepted

This is the most space-efficient approach while maintaining clarity and speed.

📊

All Approaches - One-Glance Tradeoffs

💡 In interviews, coding bottom-up tabulation or space optimized DP is usually best. Brute force is only for explanation.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(2^(m+n))	O(m+n) recursion stack	Yes (deep recursion)	Yes, but inefficient	Mention only - never code
2. Top-Down Memoization	O(m*n)	O(m*n) memo + recursion stack	Possible for large grids	Yes, with memo	Good for explaining optimization
3. Bottom-Up Tabulation	O(m*n)	O(m*n)	No	Yes, with parent pointers	Preferred for clarity and reliability
4. Space Optimized Bottom-Up	O(m*n)	O(n)	No	Harder, needs extra logic	Best for space efficiency if asked

💼

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

Clarify problem constraints and input/output format.Explain brute force recursion to show understanding of the problem.Introduce memoization to optimize recursion.Present bottom-up tabulation for iterative clarity.Finally, show space optimization to demonstrate mastery.

Time Allocation

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

What the Interviewer Tests

Interviewer tests your understanding of DP concepts, ability to optimize naive solutions, and clarity in explaining tradeoffs.

Common Follow-ups

• What if you can move diagonally? → Adjust recurrence to include dp[i-1][j-1]
• How to reconstruct the path? → Store parent pointers or reconstruct from dp table
• Can you solve it in-place? → Modify input grid to store dp values
• What if negative costs are allowed? → DP still works, but watch for cycles if moves allowed in all directions

💡 These follow-ups test your ability to adapt the DP solution to variations and optimize further.

🔍

Pattern Recognition

When to Use

1) Problem involves grid or matrix, 2) Need to find minimum or maximum path sum, 3) Moves restricted to right/down or similar, 4) Overlapping subproblems with optimal substructure.

Signature Phrases

'You can only move right or down''Find a path with minimum sum'

NOT This Pattern When

Problems with unrestricted moves or no overlapping subproblems are not this pattern.

Similar Problems

Unique Paths - counts number of paths instead of minimizing sumDungeon Game - similar grid DP with health constraintsCoin Change 2 - different DP but similar state transitions

Practice

1. The following code attempts to solve the Triangle minimum path sum problem using bottom-up DP. Identify the line that contains a subtle bug causing incorrect results on some inputs.

medium

A. for i in range(len(triangle) - 2, -1, -1):

B. dp[j] = triangle[i][j] + min(dp[j + 1], dp[j])

C. dp = triangle[-1][:]

D. return dp[0]

Solution

1. Step 1: Examine dp update line

   The original code has dp[j] = triangle[i][j] + min(dp[j], dp[j + 1]). The buggy code swaps the min arguments to min(dp[j + 1], dp[j]) which is harmless since min is commutative.

2. Step 2: Check for index out of bounds risk

   Accessing dp[j + 1] is safe because dp length is one more than current row length, so no out-of-bounds here.

3. Step 3: Identify subtle bug

   The subtle bug is that dp is updated in place from left to right, which can cause dp[j + 1] to be already updated when used in min, leading to incorrect results.

4. Step 4: Explanation of bug

   Because dp is updated from left to right, dp[j + 1] may have been updated in the current iteration, so min(dp[j], dp[j + 1]) uses a mixed state of dp values.

5. Step 5: Correct fix

   To fix, update dp from right to left so dp[j + 1] is not yet updated when used.

6. Final Answer:

   Option B -> Option B

7. Quick Check:

   Updating dp in wrong order causes subtle bugs [OK]

Hint: Bug usually in dp update line with min or indexing [OK]

Common Mistakes:

• Swapping min arguments (harmless but suspicious)
• Index out of bounds on dp[j+1]
• Updating dp in wrong order causing overwritten values

2. The following code attempts to compute the number of unique paths in an m x n grid using a space-optimized DP approach:

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

What is the bug in this code?

medium

A. Line 3 should start loop from 0 instead of 1

B. Line 4 incorrectly doubles dp[j] instead of adding dp[j-1]

C. Line 5 should return dp[0] instead of dp[-1]

D. Line 2 initializes dp with wrong size

Solution

1. Step 1: Analyze inner loop update

   Line 4 updates dp[j] by adding dp[j] to itself, doubling the value instead of adding dp[j-1].

2. Step 2: Identify correct update

   The correct update is dp[j] += dp[j - 1] to accumulate paths from left and top cells.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Doubling dp[j] breaks path count logic -> bug at line 4 [OK]

Hint: Check dp update uses dp[j-1], not dp[j] twice [OK]

Common Mistakes:

• Using dp[j] + dp[j] instead of dp[j] + dp[j-1]
• Off-by-one errors in loops

3. Suppose the Burst Balloons problem is modified so that each balloon can be burst multiple times (reused), and bursting a balloon again yields coins based on the current adjacent balloons. Which of the following changes to the bottom-up DP approach correctly adapts to this variant?

hard

A. Switch to a stateful DP that tracks the count of bursts per balloon and use memoization over these counts

B. Modify the DP to consider only the first burst of each balloon and ignore reuse

C. Use the same interval DP but allow k to be chosen multiple times per interval

D. Use a greedy approach bursting the balloon with the maximum product of neighbors repeatedly

Solution

1. Step 1: Understand reuse impact

   Allowing multiple bursts per balloon means the problem state must track how many times each balloon has been burst, increasing complexity.

2. Step 2: Adapt DP state

   Interval DP assuming each balloon bursts once no longer works. We need a DP or memoization that tracks burst counts per balloon to correctly compute coins.

3. Step 3: Evaluate options

   Switch to a stateful DP that tracks the count of bursts per balloon and use memoization over these counts correctly proposes a stateful DP with counts and memoization. Use the same interval DP but allow k to be chosen multiple times per interval incorrectly reuses interval DP without state changes. Modify the DP to consider only the first burst of each balloon and ignore reuse ignores reuse, and D is greedy and incorrect.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Tracking burst counts is necessary for reuse variants [OK]

Hint: Reuse requires tracking burst counts, not just intervals [OK]

Common Mistakes:

• Trying naive interval DP for reuse
• Ignoring state explosion
• Using greedy for complex DP variants

4. Suppose the Dungeon Game is modified so that you can move right, down, or diagonally down-right at each step. Which of the following changes to the bottom-up DP solution correctly adapts to this variant?

hard

A. Change the dp recurrence to use min(dp[i+1][j], dp[i][j+1]) only, ignoring diagonal moves

B. Change the dp recurrence to min(dp[i+1][j], dp[i][j+1], dp[i+1][j+1]) and proceed similarly

C. Use a forward DP from start to end since diagonal moves break backward DP assumptions

D. Add an extra dimension to dp to track diagonal moves separately

Solution

1. Step 1: Understand new moves

   Allowing diagonal moves adds one more possible next cell from (i,j): (i+1,j+1).

2. Step 2: Update dp recurrence

   Minimum health needed at (i,j) depends on minimum among dp[i+1][j], dp[i][j+1], and dp[i+1][j+1].

3. Step 3: Keep backward DP approach

   Backward DP still works; just include diagonal cell in min calculation.

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Including diagonal in min ensures correct health calculation [OK]

Hint: Add diagonal cell to min in dp recurrence [OK]

Common Mistakes:

• Ignoring diagonal moves
• Switching to forward DP unnecessarily
• Adding extra dp dimensions without need

5. Suppose the problem is modified so that you can move right, down, or diagonally down-right, still avoiding obstacles. Which of the following changes to the space-optimized DP approach correctly accounts for the new diagonal move?

hard

A. Modify dp[j] += dp[j-1] to dp[j] += dp[j-1] + dp[j] without extra storage.

B. Use a 2D dp array where dp[i][j] = dp[i-1][j] + dp[i][j-1] + dp[i-1][j-1], updating in row-major order.

C. Add dp[j-1] and dp[j] plus dp[j-1] from previous row, requiring a 2D dp array to track diagonal paths.

D. Keep 1D dp array but add dp[j-1] twice to account for diagonal moves.

Solution

1. Step 1: Understand diagonal dependency

   Diagonal move depends on dp[i-1][j-1], which cannot be tracked with only 1D dp array updated in-place.

2. Step 2: Correct approach

   Use 2D dp array to store counts for all cells, updating dp[i][j] = dp[i-1][j] + dp[i][j-1] + dp[i-1][j-1], ensuring all dependencies are available.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Diagonal requires previous row and previous column info simultaneously [OK]

Hint: Diagonal moves require 2D dp to track previous row and column [OK]

Common Mistakes:

• Trying to reuse 1D dp without extra storage
• Double counting paths
• Ignoring diagonal dependency