Minimum Falling Path Sum

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

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

A falling path starts at any element in the first row and chooses the element in the next row that is either directly below or diagonally left/right. Specifically, the next element from position (row, col) will be (row + 1, col - 1), (row + 1, col), or (row + 1, col + 1).

Example 1:

Input: matrix = [[2,1,3],[6,5,4],[7,8,9]] Output: 13 Explanation: There are two falling paths with a minimum sum as shown. Example 2:

Input: matrix = [[-19,57],[-40,-5]] Output: -59 Explanation: The falling path with a minimum sum is shown.

Solution

Brute Force

For every column iterate down and find minimum sum we get by tracing all the possiblity.

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;

};

Memorization

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

/**
 * @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]);
};