Grid max sum path with dynamic programming

You are twenty minutes into an Amazon interview when the interviewer draws a grid of numbers on the whiteboard. "Imagine a delivery robot sitting in the top-left corner of a warehouse floor. It can only move down or to the right. What is the most valuable route to the bottom-right corner?" This is the grid max sum path problem, sometimes also known as Minimum Path Sum (the min variant) on other platforms. It is a staple dynamic programming question that tests whether you can recognize overlapping subproblems and build an efficient bottom-up solution.

TL;DR

Build a 2D memo table the same size as the grid. Initialize the first cell with the grid value, then fill the first row and first column with cumulative sums (since there is only one way to reach those cells). For every remaining cell, set memo[r][c] = grid[r][c] + max(memo[r-1][c], memo[r][c-1]). The answer sits in memo[m-1][n-1]. This runs in O(m * n) time and O(m * n) space.

Why This Problem Matters

Grid path problems are a gateway into two-dimensional dynamic programming. Once you understand how to fill a 2D memo table cell by cell, you can tackle a wide family of problems: unique paths, minimum path sum, edit distance, longest common subsequence. Companies like Amazon and LinkedIn favor this problem because it separates candidates who can spot optimal substructure from those who reach for brute-force recursion.

Understanding the Problem

Given an m x n grid of non-negative integers, find the path from the top-left cell to the bottom-right cell that maximizes the sum of values along the path. You may only move down or right by one cell at each step.

Here is the example grid:

From cell (0,0) with value 1, we need to reach cell (2,2) with value 9. At each step, we choose to go down or right.

Movement Constraints

From any cell (r, c), the only legal moves are down to (r+1, c) or right to (r, c+1). No backtracking, no diagonal moves.

The Optimal Path

For the example grid [[1,2,3],[4,5,6],[7,8,9]], the maximum sum path is 1 + 4 + 7 + 8 + 9 = 29:

The path goes down twice, then right twice. But how do we systematically find this without checking every possible route?

Edge Cases

1. Single cell ([[5]]): The answer is just 5
2. Single row ([[1,2,3]]): Only one path, sum all values = 6
3. Single column ([[1],[2],[3]]): Only one path, sum all values = 6
4. All zeros: The answer is 0

Why Brute Force Fails

A depth-first search would explore every path from the top-left to the bottom-right. At each cell you branch into two directions, producing a decision tree of depth m + n - 2. The total number of paths is C(m+n-2, m-1), which grows exponentially. For a 10000 x 10000 grid (the upper bound in our constraints), brute force would never finish.

The saving grace is that this problem has optimal substructure: the maximum sum to reach any cell depends only on the maximum sums to reach the cells directly above and to the left. Overlapping subproblems abound, since many paths share the same intermediate cells. This is exactly the setup where dynamic programming shines.

Solution Approach

The idea is straightforward: build a memo table where memo[r][c] stores the maximum sum achievable from (0,0) to (r,c).

Base cases:

• memo[0][0] = grid[0][0] (starting cell)
• First row: memo[0][c] = memo[0][c-1] + grid[0][c] (can only come from the left)
• First column: memo[r][0] = memo[r-1][0] + grid[r][0] (can only come from above)

Recurrence:

• For all other cells: memo[r][c] = grid[r][c] + max(memo[r-1][c], memo[r][c-1])

We pick the better of the two incoming directions, add the current cell value, and store the result. After filling the entire table, memo[m-1][n-1] holds the answer.

DP Table Evolution

Step through the animation below to see how each cell is computed. Pay attention to the arrows showing which cells contribute to each computation:

Completed Memo Table

After processing every cell, the memo table looks like this:

The bottom-right cell holds 29, which matches the path 1 + 4 + 7 + 8 + 9.

Implementation

Prefer a different language? Jump to solutions in other languages.

import java.util.stream.IntStream;

public class Solution {
  public int maxSumDp(int[][] grid) {
    // Get grid dimensions
    int rows = grid.length, cols = grid[0].length;

    // Create memo table
    int[][] memo = new int[rows][cols];

    // Base case: starting cell
    memo[0][0] = grid[0][0];

    // Fill first column (only reachable from above)
    IntStream.range(1, rows)
      .forEach(r -> memo[r][0] = memo[r - 1][0] + grid[r][0]);

    // Fill first row (only reachable from the left)
    IntStream.range(1, cols)
      .forEach(c -> memo[0][c] = memo[0][c - 1] + grid[0][c]);

    // Fill remaining cells
    for (int r = 1; r < rows; r++) {
      for (int c = 1; c < cols; c++) {
        memo[r][c] = grid[r][c] + Math.max(memo[r - 1][c], memo[r][c - 1]);
      }
    }

    return memo[rows - 1][cols - 1];
  }
}

Let's trace through the key steps for our 3x3 example:

1. memo[0][0] = 1 (copy the starting value)
2. First column: memo[1][0] = 1 + 4 = 5, memo[2][0] = 5 + 7 = 12
3. First row: memo[0][1] = 1 + 2 = 3, memo[0][2] = 3 + 3 = 6
4. Inner cells: memo[1][1] = 5 + max(3, 5) = 10, and so on
5. Final answer: memo[2][2] = 9 + max(16, 20) = 29

Complexity Analysis

Time Complexity: O(m * n)

We visit each cell exactly once. For each cell, we perform a constant-time comparison and addition. The total work is proportional to the number of cells in the grid.

Space Complexity: O(m * n)

The memo table uses the same dimensions as the input grid. If you need to optimize space, you can reduce this to O(n) by keeping only the current and previous rows, since each cell depends only on the cell above and the cell to the left.

Common Pitfalls

1. Forgetting the base cases. If you skip initializing the first row and first column, the max(memo[r-1][c], memo[r][c-1]) call will read uninitialized values (zeros in Java, but wrong in languages where arrays hold garbage).

2. Confusing min and max. The minimum path sum variant uses min instead of max. Double-check which version your interviewer is asking for.

3. Off-by-one on dimensions. grid.length gives rows, grid[0].length gives columns. Swapping them leads to array index out-of-bounds errors on non-square grids.

4. Modifying the input grid. Some candidates write directly into the input grid to save space. This works but mutates the caller's data. In an interview, mention this tradeoff and ask whether the input can be modified.

Interview Tips

When this problem comes up:

1. Clarify constraints. "Can the grid contain negative numbers?" (Not in our version.) "Can I modify the input grid?" "What are the grid dimensions?"

2. Mention the brute force first. "A DFS would explore all paths, but that is exponential. Since the problem has optimal substructure and overlapping subproblems, we can use DP to solve it in O(m * n)."

3. Draw the memo table. Sketch a small 3x3 example and fill in values by hand. This demonstrates your understanding and catches errors before you code.

4. Discuss the space optimization. After presenting the O(m * n) solution, mention that you can reduce space to O(n) by using a single row. Interviewers love seeing candidates think about optimization without being prompted.

5. Handle follow-ups. Common follow-ups include: "What if you could also move diagonally?", "What if some cells are blocked?", "How would you reconstruct the actual path?"

Solutions in Other Languages

Python

class Solution:
    def max_sum_dp(self, grid):
        rows, cols = len(grid), len(grid[0])
        memo = [[0 for _ in range(cols)] for _ in range(rows)]
        memo[0][0] = grid[0][0]

        for r in range(1, rows):
            memo[r][0] = memo[r - 1][0] + grid[r][0]

        for c in range(1, cols):
            memo[0][c] = memo[0][c - 1] + grid[0][c]

        for r in range(1, rows):
            for c in range(1, cols):
                memo[r][c] = grid[r][c] + max(memo[r - 1][c], memo[r][c - 1])

        return memo[rows - 1][cols - 1]

JavaScript

class Solution {
  maxSumDp(grid) {
    const rows = grid.length, cols = grid[0].length;
    const memo = [...Array(rows)].map(_ => Array(cols));
    memo[0][0] = grid[0][0];

    for (let r = 1; r < rows; r++) {
      memo[r][0] = memo[r - 1][0] + grid[r][0];
    }

    for (let c = 1; c < cols; c++) {
      memo[0][c] = memo[0][c - 1] + grid[0][c];
    }

    for (let r = 1; r < rows; r++) {
      for (let c = 1; c < cols; c++) {
        memo[r][c] = grid[r][c] + Math.max(memo[r - 1][c], memo[r][c - 1]);
      }
    }

    return memo[rows - 1][cols - 1];
  }
}

TypeScript

class Solution {
  maxSumDp(grid: number[][]): number {
    const rows = grid.length, cols = grid[0].length;
    const memo: number[][] = [...Array(rows)].map(_ => Array(cols));
    memo[0][0] = grid[0][0];

    for (let r = 1; r < rows; r++) {
      memo[r][0] = memo[r - 1][0] + grid[r][0];
    }

    for (let c = 1; c < cols; c++) {
      memo[0][c] = memo[0][c - 1] + grid[0][c];
    }

    for (let r = 1; r < rows; r++) {
      for (let c = 1; c < cols; c++) {
        memo[r][c] = grid[r][c] + Math.max(memo[r - 1][c], memo[r][c - 1]);
      }
    }

    return memo[rows - 1][cols - 1];
  }
}

C++

#include <vector>
#include <algorithm>

class Solution {
public:
  int maxSumDp(std::vector<std::vector<int>> &grid) {
    int rows = grid.size(), cols = grid[0].size();
    std::vector<std::vector<int>> memo(rows, std::vector<int>(cols, 0));
    memo[0][0] = grid[0][0];

    for (int r = 1; r < rows; ++r) {
      memo[r][0] = memo[r - 1][0] + grid[r][0];
    }

    for (int c = 1; c < cols; ++c) {
      memo[0][c] = memo[0][c - 1] + grid[0][c];
    }

    for (int r = 1; r < rows; ++r) {
      for (int c = 1; c < cols; ++c) {
        memo[r][c] = grid[r][c] + std::max(memo[r - 1][c], memo[r][c - 1]);
      }
    }

    return memo[rows - 1][cols - 1];
  }
};

Go

func MaxSumDp(grid [][]int) int {
    rows, cols := len(grid), len(grid[0])
    memo := make([][]int, rows)
    for i := range memo {
        memo[i] = make([]int, cols)
    }
    memo[0][0] = grid[0][0]

    for r := 1; r < rows; r++ {
        memo[r][0] = memo[r-1][0] + grid[r][0]
    }

    for c := 1; c < cols; c++ {
        memo[0][c] = memo[0][c-1] + grid[0][c]
    }

    for r := 1; r < rows; r++ {
        for c := 1; c < cols; c++ {
            if memo[r-1][c] > memo[r][c-1] {
                memo[r][c] = grid[r][c] + memo[r-1][c]
            } else {
                memo[r][c] = grid[r][c] + memo[r][c-1]
            }
        }
    }

    return memo[rows-1][cols-1]
}

Scala

class Solution {
  def maxSumDp(grid: Array[Array[Int]]): Int = {
    val (rows, cols) = (grid.length, grid(0).length)
    val memo = Array.ofDim[Int](rows, cols)
    memo(0)(0) = grid(0)(0)

    Range(1, rows).foreach(r => memo(r)(0) = memo(r - 1)(0) + grid(r)(0))
    Range(1, cols).foreach(c => memo(0)(c) = memo(0)(c - 1) + grid(0)(c))

    for (r <- 1 until rows) {
      for (c <- 1 until cols) {
        memo(r)(c) = grid(r)(c) + Math.max(memo(r - 1)(c), memo(r)(c - 1))
      }
    }

    memo(rows - 1)(cols - 1)
  }
}

Kotlin

class Solution {
    fun maxSumDp(grid: Array<IntArray>): Int {
        val rows = grid.size
        val cols = grid[0].size
        val memo = Array(rows) { IntArray(cols) }
        memo[0][0] = grid[0][0]

        for (r in 1 until rows) {
            memo[r][0] = memo[r - 1][0] + grid[r][0]
        }

        for (c in 1 until cols) {
            memo[0][c] = memo[0][c - 1] + grid[0][c]
        }

        for (r in 1 until rows) {
            for (c in 1 until cols) {
                memo[r][c] = grid[r][c] + maxOf(memo[r - 1][c], memo[r][c - 1])
            }
        }

        return memo[rows - 1][cols - 1]
    }
}

Swift

class Solution {
    func maxSumDp(_ grid: [[Int]]) -> Int {
        let rows = grid.count
        let cols = grid[0].count
        var memo = Array(repeating: Array(repeating: 0, count: cols), count: rows)
        memo[0][0] = grid[0][0]

        for r in 1..<rows {
            memo[r][0] = memo[r - 1][0] + grid[r][0]
        }

        for c in 1..<cols {
            memo[0][c] = memo[0][c - 1] + grid[0][c]
        }

        for r in 1..<rows {
            for c in 1..<cols {
                memo[r][c] = grid[r][c] + max(memo[r - 1][c], memo[r][c - 1])
            }
        }

        return memo[rows - 1][cols - 1]
    }
}

Ruby

class Solution
  def max_sum_dp(grid)
    rows, cols = grid.length, grid[0].length
    memo = Array.new(rows) { Array.new(cols, 0) }
    memo[0][0] = grid[0][0]

    (1...rows).each { |r| memo[r][0] = memo[r - 1][0] + grid[r][0] }
    (1...cols).each { |c| memo[0][c] = memo[0][c - 1] + grid[0][c] }

    (1...rows).each do |r|
      (1...cols).each do |c|
        memo[r][c] = grid[r][c] + [memo[r - 1][c], memo[r][c - 1]].max
      end
    end

    memo[rows - 1][cols - 1]
  end
end

Rust

pub fn max_sum_dp(grid: Vec<Vec<i32>>) -> i32 {
    let rows = grid.len();
    let cols = grid[0].len();
    let mut memo = vec![vec![0; cols]; rows];
    memo[0][0] = grid[0][0];

    for r in 1..rows {
        memo[r][0] = memo[r - 1][0] + grid[r][0];
    }

    for c in 1..cols {
        memo[0][c] = memo[0][c - 1] + grid[0][c];
    }

    for r in 1..rows {
        for c in 1..cols {
            memo[r][c] = grid[r][c] + memo[r - 1][c].max(memo[r][c - 1]);
        }
    }

    memo[rows - 1][cols - 1]
}

C#

using System;

public class Solution {
    public int MaxSumDp(int[][] grid) {
        int rows = grid.Length, cols = grid[0].Length;
        var memo = new int[rows][];
        for (int i = 0; i < rows; i++) {
            memo[i] = new int[cols];
        }
        memo[0][0] = grid[0][0];

        for (int r = 1; r < rows; r++) {
            memo[r][0] = memo[r - 1][0] + grid[r][0];
        }

        for (int c = 1; c < cols; c++) {
            memo[0][c] = memo[0][c - 1] + grid[0][c];
        }

        for (int r = 1; r < rows; r++) {
            for (int c = 1; c < cols; c++) {
                memo[r][c] = grid[r][c] + Math.Max(memo[r - 1][c], memo[r][c - 1]);
            }
        }

        return memo[rows - 1][cols - 1];
    }
}

Dart

import 'dart:math';

class Solution {
  int maxSumDp(List<List<int>> grid) {
    int rows = grid.length, cols = grid[0].length;
    List<List<int>> memo = List.generate(rows, (_) => List.filled(cols, 0));
    memo[0][0] = grid[0][0];

    for (int r = 1; r < rows; r++) {
      memo[r][0] = memo[r - 1][0] + grid[r][0];
    }

    for (int c = 1; c < cols; c++) {
      memo[0][c] = memo[0][c - 1] + grid[0][c];
    }

    for (int r = 1; r < rows; r++) {
      for (int c = 1; c < cols; c++) {
        memo[r][c] = grid[r][c] + max(memo[r - 1][c], memo[r][c - 1]);
      }
    }

    return memo[rows - 1][cols - 1];
  }
}

PHP

class Solution {
    public function maxSumDp(array $grid): int {
        $rows = count($grid);
        $cols = count($grid[0]);
        $memo = array_fill(0, $rows, array_fill(0, $cols, 0));
        $memo[0][0] = $grid[0][0];

        for ($r = 1; $r < $rows; $r++) {
            $memo[$r][0] = $memo[$r - 1][0] + $grid[$r][0];
        }

        for ($c = 1; $c < $cols; $c++) {
            $memo[0][$c] = $memo[0][$c - 1] + $grid[0][$c];
        }

        for ($r = 1; $r < $rows; $r++) {
            for ($c = 1; $c < $cols; $c++) {
                $memo[$r][$c] = $grid[$r][$c] + max($memo[$r - 1][$c], $memo[$r][$c - 1]);
            }
        }

        return $memo[$rows - 1][$cols - 1];
    }
}

Key Takeaways

• The grid max sum path problem is solved by building a 2D memo table where each cell stores the best achievable sum from the top-left corner, using the recurrence memo[r][c] = grid[r][c] + max(memo[r-1][c], memo[r][c-1]).
• First row and first column cells have only one incoming direction, so their memo values are cumulative sums. Forgetting to initialize these is the most common bug.
• Time and space are both O(m * n), but space can be optimized to O(n) by keeping only the current row since each cell depends only on the cell above and the cell to the left.
• This problem is the gateway to 2D dynamic programming. The same table-filling pattern appears in minimum path sum, edit distance, longest common subsequence, and dozens of other DP problems.
• In interviews, always mention the brute-force exponential approach first, then explain why DP works (optimal substructure + overlapping subproblems). This shows structured thinking.

Practice and Related Problems

Once you are comfortable with grid max sum path, try these related problems to deepen your DP skills:

• Count paths on a board (counting unique paths instead of maximizing sum)
• Minimum sum path in a triangle
• Leap to the finish line (1D DP variant)

Remember, consistent practice is the key to succeeding in coding interviews. This problem and thousands of others are available on Firecode, where over 50,000 users have successfully prepared for technical interviews and landed six and seven-figure jobs at top tech companies.