~/DHRUVUpskilling
← board/DSA/Dynamic Programming/dsa-dynamic-programming-10
Solved·02 Oct

Minimum Falling Path Sum

DifficultyMedium
PatternDynamic Programming
TrackDSA
tl;dr

find minimum sum while coming down in a grid, you can either go down , or down left or down right

full write-up

Minimum Falling Path Sum

Problem Statement

Given an n x n array of integers, matrix, return the minimum sum of any falling path through the matrix.

A falling path starts at any element in the first row, and at each step, moves to the element in the next row that is either directly below, or diagonally left/right. Specifically, from position (row, col), the next step can go to (row + 1, col - 1), (row + 1, col), or (row + 1, col + 1).

Examples

Example 1

Input: matrix = [[2,1,3],[6,5,4],[7,8,9]]

Output: 13

Explanation: There are two falling paths that both produce this minimum sum.

Example 2

Input: matrix = [[-19,57],[-40,-5]]

Output: -59

Explanation: The falling path with the minimum sum is shown.

Solution

Brute Force

For every possible starting column in the first row, we trace downward through all the possible paths, and find the minimum sum among them.

  • At each cell, we try the three possible moves to the next row (down-left, down, down-right), and take whichever leads to the smallest total.
  • If a move would go out of bounds (off the left or right edge of the matrix), we treat that option as Infinity, so it never gets chosen.
  • The base case is the last row, where a cell's value is simply itself.
var minFallingPathSum = function (matrix) {
    let m = matrix.length;
    let n = matrix[0].length;
    let minimum = Infinity;

    function recurr(i, j) {

        if (j < 0 || j >= n) {
            return Infinity;
        }

        if (i === m - 1) {
            return matrix[i][j];
        }

        let downLeft = recurr(i + 1, j - 1);
        let down = recurr(i + 1, j);
        let dowRight = recurr(i + 1, j + 1);

        const bestNext = Math.min(downLeft, down, dowRight);
        return matrix[i][j] + bestNext;
    }

    let answer = Infinity;
    for (let col = 0; col < n; col++) {

        let pathSum = recurr(0, col);
        answer = Math.min(pathSum, answer);
    }

    return answer;
};

Memoization (Top-Down)

Same approach as the brute force version, but we store each cell's result the first time we calculate it, so we never recompute the same path twice.

var minFallingPathSum = function (matrix) {
    let m = matrix.length;
    let n = matrix[0].length;
    let minimum = Infinity;

    function recurr(i, j, dp) {

        if (j < 0 || j >= n) {
            return Infinity;
        }
        if (dp[i][j] !== undefined) {
            return dp[i][j];
        }
        if (i === m - 1) {
            return matrix[i][j];
        }

        let downLeft = recurr(i + 1, j - 1, dp);
        let down = recurr(i + 1, j, dp);
        let dowRight = recurr(i + 1, j + 1, dp);

        const bestNext = Math.min(downLeft, down, dowRight);
        dp[i][j] = matrix[i][j] + bestNext;
        return dp[i][j];
    }

    let dp = Array.from({ length: m }, () => Array(n).fill(undefined));

    let answer = Infinity;
    for (let col = 0; col < n; col++) {

        let pathSum = recurr(0, col, dp);
        answer = Math.min(pathSum, answer);
    }

    return answer;
};

Tabulation (Bottom-Up)

This version builds the answer going forward, starting from the first row and working down, rather than starting from the end and recursing backward.

  • For the first row, each cell's value in dp is simply its own value in matrix.
  • For every other row, each cell looks at the three cells above it (up-left, up, up-right) from the previous row, and adds the smallest of those to its own value.
  • If a cell is at the left edge or right edge of the matrix, the missing diagonal neighbor is treated as an extremely large number (1e9), so it's never mistakenly chosen as the minimum.
  • At the end, the answer is the smallest value found anywhere in the last row of dp.
/**
 * @param {number[][]} matrix
 * @return {number}
 */
var minFallingPathSum = function (matrix) {
    let m = matrix.length;
    let n = matrix[0].length;

    let dp = Array.from(
        { length: m },
        () => Array(n).fill(0)
    );

    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {

            // First row
            if (i === 0) {
                dp[i][j] = matrix[i][j];
            }
            else {

                // Up-left
                let upLeft = matrix[i][j];

                if (j > 0) {
                    upLeft += dp[i - 1][j - 1];
                } else {
                    upLeft += 1e9;
                }

                // Up
                let up = matrix[i][j] + dp[i - 1][j];

                // Up-right
                let upRight = matrix[i][j];

                if (j < n - 1) {
                    upRight += dp[i - 1][j + 1];
                } else {
                    upRight += 1e9;
                }

                dp[i][j] = Math.min(
                    upLeft,
                    up,
                    upRight
                );
            }
        }
    }

    return Math.min(...dp[m - 1]);
};
Minimum Falling Path Sum — pattern notes — Dhruv Parmar