931. Minimum Falling Path Sum

source: https://leetcode.com/problems/minimum-falling-path-sum/

Question

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).

暴力法

拆分成重叠的子问题：

• 本次的最优解=选取上一行的三个点的最优解的最小值

同时增加备忘录，对迭代树剪枝。

/**
 * 暴力递归+备忘录
 * @param {number[][]} matrix
 * @return {number}
 */
var minFallingPathSum = function (matrix) {
    const lastLinePositionArr = [[-1, 0], [-1, -1], [-1, 1]];
    const cache = {};
    const find = ([y, x]) => {
        const v = matrix[y][x];
        if (v === undefined) return null;
        if (y === 0) return v;
        let ret = Infinity;
        for (let i = 0; i < lastLinePositionArr.length; i++) {
            const lastY = y + lastLinePositionArr[i][0];
            const lastX = x + lastLinePositionArr[i][1];
            const key = `${[lastY, lastX]}`;
            if (cache[key] === undefined) cache[key] = find([lastY, lastX]);
            if (cache[key] !== null) ret = Math.min(cache[key] + v, ret);
        }
        return ret;
    };
    let ret = Infinity;
    const y = matrix.length - 1;
    for (let x = 0; x < matrix[0].length; x++) ret = Math.min(find([y, x]), ret);
    return ret;
};

dp

既然是重叠子问题，很明显也可以用dp来解。

先明确一下dp时的定义：

• 明确状态：转移的状态应该是点位[y,x]
• 确定dp数组定义：dp[n]代表当前行为n的最优解数组
• 明确选择：从上一行的三个点位中选择相加最小的点位
• 明确base case：目标行为0时，返回当前值

/**
 * dp
 * @param {number[][]} matrix
 * @return {number}
 */
var minFallingPathSum = function (matrix) {
    const lastLinePositionArr = [-1, 0, 1];
    const dp = new Array(matrix.length);
    dp[0] = [...matrix[0]];
    for (let i = 1; i < matrix.length; i++) {
        dp[i] = [...matrix[i]].map((v, index) => {
            let ret = Infinity;
            lastLinePositionArr.forEach(last => {
                const x = last + index;
                if (dp[i - 1]?.[x] !== undefined) ret = Math.min(dp[i - 1][x], ret);
            });
            return ret + v;
        });
    }
    return dp[matrix.length - 1].sort((a, b) => a - b)[0];
};

总结

只要能整理出子问题，和如果转移子问题，那么dp类的题目就会很简单。