Start learning free

LESSON 273 OF 347 · MEMOIZATION

Minimum Path Sum in C#: Memoized Recursion on an int[,] Grid

Practice O(n2) - Memoization Read the full explanation

Given a 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.

Note: You can only move either down or right at any point in time.

Example:

Input:
[
  [1,3,1],
  [1,5,1],
  [4,2,1]
]
Output: 7
Explanation: Because the path 1→3→1→1→1 minimizes the sum.

Note:

Convert the previous solution to an iterative one. Your algorithm should run in O(n * m) time and use O(n * m) extra space.

STEP 1 OF 8
    Ctrl + Enter to check

    C# · MEMOIZATION

    Minimum Path Sum in C#, explained

    Problem overview

    You get a grid of non-negative integers with m rows and n columns. Starting at the top-left cell, you move only down or right until you reach the bottom-right cell. The method MinPathSum returns the smallest possible sum of the numbers on the cells you visit, including both ends.

    For this grid the answer is 7:

    1 3 1
1 5 1
4 2 1

    The path 1, 3, 1, 1, 1 (right, right, down, down) adds up to 7, and no other down/right path does better. This lesson solves it with recursion and a cache, in O(n * m) time and O(n * m) extra space.

    Approach: the best path from a cell

    Define MinSum(grid, cache, i, j) as the minimum path sum from cell (i, j) to the bottom-right corner. From any cell other than the corner you can only go down or right, so the best path is the cell's own value plus the better of the two continuations:

    MinSum(i, j) = grid[i, j] + min(MinSum(i + 1, j), MinSum(i, j + 1))

    If a move leaves the grid, that continuation doesn't exist. Returning int.MaxValue for it means the minimum never prefers it. If you are standing on the bottom-right cell, the path is that cell alone.

    The plain recursion is slow because many paths cross the same cell. In a 3 x 3 grid, cell (1, 1) is reached from both (0, 1) and (1, 0), and its whole subtree is solved twice; in bigger grids the repetition multiplies. The answer for a cell never changes, so we store it in a 2D array shaped like the grid, cache, and reuse it. Each of the m * n cells is then computed once.

    On the example, the values stored are 3 at (2, 1), 7 at (2, 0), 2 at (1, 2), 7 at (1, 1), 8 at (1, 0), 3 at (0, 2) and 6 at (0, 1). The top-left cell then gives 1 + min(8, 6) = 7.

    Step by step

    1. Create the cache in MinPathSum as an int[,] with the same dimensions as the grid: new int[grid.GetLength(0), grid.GetLength(1)]. It starts filled with zeros.
    2. Return the helper's answer for the start cell: MinSum(grid, cache, 0, 0).
    3. Declare the helper above MinPathSum, taking the grid, the cache and the indices i and j.
    4. Out of bounds: if i is past the last row or j past the last column, return int.MaxValue.
    5. Base case: on the bottom-right cell, return grid[i, j]. Do this before using the cache, since the corner is never stored.
    6. Cache hit: if cache[i, j] is greater than 0, the cell was already computed, so return it. A cell still holding 0 has not been filled yet.
    7. Compute and store the recurrence in cache[i, j], using Math.Min on the answers for the cell below and the cell to the right.
    8. Return cache[i, j].

    The solution in C#

    class Solution {
    public int MinSum(int[,] grid, int[,] cache, int i, int j) {
        if (i >= grid.GetLength(0) || j >= grid.GetLength(1)) {
            return int.MaxValue;
        }
        if (i == grid.GetLength(0) - 1 && j == grid.GetLength(1) - 1) {
            return grid[i, j];
        }
        if (cache[i, j] > 0) {
            return cache[i, j];
        }
        cache[i, j] =
        grid[i, j] + Math.Min(MinSum(grid, cache, i + 1, j), MinSum(grid, cache, i, j + 1));
        return cache[i, j];
    }

    public int MinPathSum(int[,] grid) {
        int[,] cache = new int[grid.GetLength(0), grid.GetLength(1)];
        return MinSum(grid, cache, 0, 0);
    }
};

    C# details worth knowing

    • Rectangular arrays. int[,] is a true two-dimensional array, indexed as grid[i, j] with a comma. It is different from a jagged array int[][], which is indexed as grid[i][j]. Using the wrong syntax is a compile error.
    • Sizes with GetLength. A rectangular array's Length is the total number of cells. To get the rows use GetLength(0) and for the columns GetLength(1).
    • Zero as "not computed". New arrays are zero-filled, and this code treats 0 as "empty". A cell whose real answer is 0 (a path of all zeros) is never recognized as cached, so it is simply recomputed. The result is still correct, only slower for such cells.
    • The large sentinel is safe. int.MaxValue is never added to anything: the only cell that could have both moves out of bounds is the bottom-right one, and it returns first. Adding to int.MaxValue would wrap around to a negative number.

    Complexity

    There are m * n cells. Each is computed once, and the work for a cell besides its two recursive calls is constant, while every repeated request is a cache hit. The time is O(n * m). The cache has m * n entries and the recursion is at most m + n calls deep, so the extra space is O(n * m).

    Edge cases and common mistakes

    • A single cell. The start is the bottom-right cell, so the method returns that cell's value.
    • A single row or column. One of the two moves is always out of bounds and returns int.MaxValue, so the path is forced. For the row [1, 2, 3] the answer is 6.
    • Checking the cache before the bounds. Reading cache[i, j] with i or j out of range throws IndexOutOfRangeException. Test the bounds first.
    • Using grid.Length as the row count. It is the cell count (9 for a 3 x 3 grid), not the number of rows.
    • Forgetting to share the cache. Creating a new array inside the helper discards all previous work.
    Keep going with C#About 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free