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. Consider the following Python code implementing the Cherry Pickup problem using bottom-up DP. Given the input grid below, what is the final returned value?

grid = [
  [0, 1, -1],
  [1, 0, -1],
  [1, 1,  1]
]

from typing import List

def cherryPickup(grid: List[List[int]]) -> int:
    n = len(grid)
    dp = [[[-float('inf')] * n for _ in range(n)] for __ in range(n)]
    dp[0][0][0] = grid[0][0]
    for step in range(1, 2 * (n - 1) + 1):
        for r1 in range(max(0, step - (n - 1)), min(n, step + 1)):
            c1 = step - r1
            if c1 < 0 or c1 >= n:
                continue
            for r2 in range(max(0, step - (n - 1)), min(n, step + 1)):
                c2 = step - r2
                if c2 < 0 or c2 >= n:
                    continue
                if grid[r1][c1] == -1 or grid[r2][c2] == -1:
                    continue
                candidates = []
                if r1 > 0 and r2 > 0:
                    candidates.append(dp[r1 - 1][c1][r2 - 1])
                if r1 > 0 and c2 > 0:
                    candidates.append(dp[r1 - 1][c1][r2])
                if c1 > 0 and r2 > 0:
                    candidates.append(dp[r1][c1 - 1][r2 - 1])
                if c1 > 0 and c2 > 0:
                    candidates.append(dp[r1][c1 - 1][r2])
                best_prev = max(candidates) if candidates else -float('inf')
                if best_prev == -float('inf'):
                    continue
                val = best_prev + grid[r1][c1]
                if r1 != r2:
                    val += grid[r2][c2]
                dp[r1][c1][r2] = max(dp[r1][c1][r2], val)
    return max(0, dp[n - 1][n - 1][n - 1])

print(cherryPickup(grid))

easy

A. 6

B. 5

C. 4

D. 3

Solution

1. Step 1: Trace dp states for step=4 (final step for 3x3 grid)

   At step=4, both players reach bottom-right (2,2). The dp value dp[2][2][2] accumulates max cherries collected along valid paths avoiding thorns (-1).

2. Step 2: Calculate max cherries collected

   By tracing paths, max cherries collected is 6, considering both players' paths and avoiding double counting.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Manual path tracing confirms max cherries = 6 [OK]

Hint: Trace dp at final step for both players [OK]

Common Mistakes:

• Off-by-one errors in step or indices
• Double counting cherries when players overlap
• Ignoring thorn cells leading to invalid paths

2. Consider the following bottom-up DP code for the Triangle minimum path sum problem. Given the input triangle = [[2],[3,4],[6,5,7]], what is the value of dp after the first iteration of the outer loop (i = 1)?

easy

A. [8, 9, 7]

B. [9, 10, 7]

C. [11, 10, 7]

D. [7, 9, 7]

Solution

1. Step 1: Initialize dp with last row

   dp = [6, 5, 7]

2. Step 2: Compute dp for i=1 (row [3,4])

   For j=0: dp[0] = 3 + min(6,5) = 3 + 5 = 8 For j=1: dp[1] = 4 + min(5,7) = 4 + 5 = 9 Updated dp = [8, 9, 7]

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   dp updated correctly for row 1 [OK]

Hint: dp[j] updated using min of dp[j], dp[j+1] from row below [OK]

Common Mistakes:

• Off-by-one error in indexing dp
• Not copying last row correctly
• Mixing up dp[j] and dp[j+1] in min calculation

3. You need to find the number of distinct ways to move from the top-left corner to the bottom-right corner of an m x n grid, moving only down or right at each step. Which algorithmic approach guarantees an efficient and optimal solution for this problem?

easy

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

B. Greedy algorithm that always moves towards the direction with fewer remaining steps

C. Dynamic Programming that builds solutions from smaller subproblems using a grid-based state representation

D. Divide and conquer by splitting the grid into quadrants and combining results

Solution

1. Step 1: Understand problem constraints

   The problem requires counting all unique paths with only right and down moves, which naturally forms overlapping subproblems.

2. Step 2: Identify suitable approach

   Dynamic Programming efficiently solves overlapping subproblems by storing intermediate results, unlike greedy or pure recursion which are either incorrect or inefficient.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   DP uses subproblem reuse -> optimal and efficient [OK]

Hint: Counting paths with overlapping subproblems -> DP [OK]

Common Mistakes:

• Thinking greedy can find all paths
• Using pure recursion without memoization

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

5. What is the time complexity of the space-optimized bottom-up DP solution for the Maximal Square problem on an m x n matrix, and why might some candidates incorrectly think it is higher?

medium

A. O(m^3) because checking all squares requires nested loops

B. O(m * n * min(m,n)) because of checking all possible square sizes

C. O(m * n) because each cell is processed once with constant time updates

D. O(m + n) because only rows and columns are iterated separately

Solution

1. Step 1: Identify loops in the code

   Two nested loops iterate over rows and columns, each cell processed once.

2. Step 2: Understand DP update cost

   Each dp update is O(1), no nested checks for squares inside loops.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   DP avoids checking all squares explicitly [OK]

Hint: DP processes each cell once with constant work [OK]

Common Mistakes:

• Confusing brute force with DP complexity
• Assuming nested loops check all squares
• Ignoring constant time DP updates