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. You are given a convex polygon with n vertices, each vertex having an associated value. The goal is to triangulate the polygon such that the sum of the products of the values of the vertices of each triangle is minimized. Which algorithmic approach guarantees finding the optimal solution efficiently?

easy

A. Divide and conquer by splitting the polygon into two halves and solving independently

B. A greedy algorithm that always picks the triangle with the smallest immediate product first

C. A simple depth-first search without memoization that explores all triangulations

D. Dynamic programming over intervals that considers all possible triangulations and chooses the minimal cost

Solution

1. Step 1: Understand problem structure

   The problem requires considering all possible triangulations to find the minimal sum of triangle costs, which depends on intervals of vertices.

2. Step 2: Identify suitable algorithm

   Dynamic programming over intervals (interval DP) systematically explores all sub-polygons and stores minimal costs, ensuring optimality.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Interval DP is the classic approach for polygon triangulation problems [OK]

Hint: Interval DP handles overlapping subproblems optimally [OK]

Common Mistakes:

• Greedy fails due to local minima
• DFS without memoization is exponential
• Divide and conquer ignores polygon connectivity

2. Consider the following code for minimum score triangulation of a polygon with vertex values [1, 3, 1, 4]. What is the final returned value?

easy

A. 7

B. 12

C. 10

D. 13

Solution

1. Step 1: Trace dp for length=3 (triangles)

   For i=0,j=2: dp[0][2] = 1*3*1=3; for i=1,j=3: dp[1][3] = 3*1*4=12

2. Step 2: Trace dp for length=4 (whole polygon)

   For i=0,j=3, k=1: cost=dp[0][1]+dp[1][3]+1*3*4=0+12+12=24; k=2: cost=dp[0][2]+dp[2][3]+1*1*4=3+0+4=7; dp[0][3]=7

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Minimal triangulation cost is 7, not 9 or higher [OK]

Hint: Check all k splits for minimal dp[i][j] cost [OK]

Common Mistakes:

• Off-by-one in loops
• Ignoring dp initialization
• Wrong triangle cost calculation

3. What is the time complexity of the space-optimized bottom-up DP solution for the Cheapest Flights Within K Stops problem, given n cities, E flights, and maximum K stops?

medium

A. O(K * E) because each iteration relaxes all edges up to K+1 times

B. O(n^3) due to nested loops over cities and stops

C. O(E * log n) similar to Dijkstra's algorithm

D. O(n * K^2) due to dynamic programming over stops and cities

Solution

1. Step 1: Identify loops in the algorithm

   The outer loop runs K+1 times, and the inner loop iterates over all E flights to relax edges.

2. Step 2: Calculate total complexity

   Each iteration processes E edges, so total time is O(K * E). No nested loops over n^2 or log factors appear.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Algorithm iterates over edges K+1 times [OK]

Hint: Outer loop K+1 times, inner loop over E edges [OK]

Common Mistakes:

• Confusing E with n^2
• Assuming Dijkstra complexity
• Counting recursion stack space

4. Suppose the problem is modified so that you can take unlimited flights (reuse edges) but still want the cheapest price within K stops. Which modification to the bottom-up DP approach correctly handles this variant?

hard

A. Use Bellman-Ford algorithm with K+1 iterations allowing edge reuse in each iteration

B. Switch to Dijkstra's algorithm since unlimited reuse removes stop constraints

C. Modify DP to allow updating curr[v] multiple times per iteration by relaxing edges repeatedly until no changes

D. Use the same bottom-up DP but increase iterations to K+1 without changes

Solution

1. Step 1: Understand the unlimited reuse variant

   Unlimited reuse means cycles are allowed, so shortest path with stop constraints resembles Bellman-Ford relaxation over K+1 iterations.

2. Step 2: Identify correct algorithm

   Bellman-Ford naturally handles edge reuse and negative cycles (if any), iterating K+1 times to relax edges, matching problem constraints.

3. Step 3: Why other options fail

   Use the same bottom-up DP but increase iterations to K+1 without changes ignores edge reuse effect; Switch to Dijkstra's algorithm since unlimited reuse removes stop constraints ignores stop constraints; Modify DP to allow updating curr[v] multiple times per iteration by relaxing edges repeatedly until no changes suggests repeated relaxation within iteration, which is inefficient and incorrect.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Bellman-Ford with K+1 iterations handles unlimited reuse correctly [OK]

Hint: Bellman-Ford handles edge reuse with K+1 relaxations [OK]

Common Mistakes:

• Using Dijkstra ignoring stops
• Not increasing iterations
• Trying repeated relaxations inside iteration

5. Suppose the problem is modified so that the matrix can contain '1's and '0's, but you want to find the largest square containing only '1's where you are allowed to flip at most one '0' inside the square to '1'. Which of the following approaches correctly adapts the DP solution to handle this variant efficiently?

hard

A. Maintain two DP arrays: one for squares with zero flips and one for squares with one flip allowed, updating both simultaneously

B. Use the original DP but treat all '0's as '1's to allow flipping implicitly

C. Run the original DP multiple times, each time flipping a different '0' to '1' and taking the max result

D. Use a greedy approach to find the largest square ignoring zeros, then check if flipping one zero inside is possible

Solution

1. Step 1: Understand the variant

   Allowing one flip means tracking squares formed with zero or one zero flipped inside.

2. Step 2: Adapt DP states

   Maintain two DP states per cell: max square size without flips and with one flip used, updating both based on neighbors.

3. Step 3: Reject naive approaches

   Original DP ignores flips; multiple runs are inefficient; greedy ignores DP dependencies.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Two DP arrays track flip states efficiently [OK]

Hint: Track DP states with and without flips [OK]

Common Mistakes:

• Ignoring flip state in DP
• Trying multiple brute force runs
• Using greedy without DP