typescript 解法, 执行用时: 80 ms, 内存消耗: 45.7 MB, 提交时间: 2023-08-10 09:53:20

function minFallingPathSum(grid: number[][]): number {
    let [f, g, fp] = [0, 0, -1];
    const inf = 1 << 30;
    for (const row of grid) {
        let [ff, gg, ffp] = [inf, inf, -1];
        for (let j = 0; j < row.length; ++j) {
            const s = (j !== fp ? f : g) + row[j];
            if (s < ff) {
                [gg, ff, ffp] = [ff, s, j];
            } else if (s < gg) {
                gg = s;
            }
        }
        [f, g, fp] = [ff, gg, ffp];
    }
    return f;
}

golang 解法, 执行用时: 28 ms, 内存消耗: 6.7 MB, 提交时间: 2023-08-10 09:53:07

func minFallingPathSum(grid [][]int) int {
	const inf = 1 << 30
	f, g := 0, 0
	fp := -1
	for _, row := range grid {
		ff, gg := inf, inf
		ffp := -1
		for j, v := range row {
			s := f
			if j == fp {
				s = g
			}
			s += v
			if s < ff {
				ff, gg, ffp = s, ff, j
			} else if s < gg {
				gg = s
			}
		}
		f, g, fp = ff, gg, ffp
	}
	return f
}

java 解法, 执行用时: 2 ms, 内存消耗: 48.5 MB, 提交时间: 2023-08-10 09:52:49

class Solution {
    public int minFallingPathSum(int[][] grid) {
        int f = 0, g = 0;
        int fp = -1;
        final int inf = 1 << 30;
        for (int[] row : grid) {
            int ff = inf, gg = inf;
            int ffp = -1;
            for (int j = 0; j < row.length; ++j) {
                int s = (j != fp ? f : g) + row[j];
                if (s < ff) {
                    gg = ff;
                    ff = s;
                    ffp = j;
                } else if (s < gg) {
                    gg = s;
                }
            }
            f = ff;
            g = gg;
            fp = ffp;
        }
        return f;
    }
}

python3 解法, 执行用时: 80 ms, 内存消耗: 18.6 MB, 提交时间: 2023-08-10 09:52:16

'''
维护三个变量 
f: 前 i 行的最小数字和
g: 第 i 行的第二小数字和
fp: 第 i 行的最小数字在第 fp 列
'''
class Solution:
    def minFallingPathSum(self, grid: List[List[int]]) -> int:
        f = g = 0
        fp = -1
        for row in grid:
            ff = gg = inf
            ffp = -1
            for j, v in enumerate(row):
                s = (g if j == fp else f) + v
                if s < ff:
                    gg = ff
                    ff = s
                    ffp = j
                elif s < gg:
                    gg = s
            f, g, fp = ff, gg, ffp
        return f

javascript 解法, 执行用时: 308 ms, 内存消耗: 44.9 MB, 提交时间: 2023-08-10 09:47:03

/**
 * @param {number[][]} grid
 * @return {number}
 */
var minFallingPathSum = function(grid) {
    const n = grid.length;
    const d = new Array(n).fill(0).map(() => new Array(n).fill(Infinity));
    for (let i = 0; i < n; i++) {
        d[0][i] = grid[0][i];
    }
    for (let i = 1; i < n; i++) {
        for (let j = 0; j < n; j++) {
            for (let k = 0; k < n; k++) {
                if (j == k) {
                    continue;
                }
                d[i][j] = Math.min(d[i][j], d[i - 1][k] + grid[i][j]);
            }
        }
    }
    return Math.min(...d[n - 1]);
};

java 解法, 执行用时: 84 ms, 内存消耗: 50.1 MB, 提交时间: 2023-08-10 09:43:09

class Solution {
    public int minFallingPathSum(int[][] grid) {
        int n = grid.length;
        int[][] d = new int[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                d[i][j] = Integer.MAX_VALUE;
            }
        }
        for (int i = 0; i < n; i++) {
            d[0][i] = grid[0][i];
        }
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < n; j++) {
                for (int k = 0; k < n; k++) {
                    if (j == k) {
                        continue;
                    }
                    d[i][j] = Math.min(d[i][j], d[i - 1][k] + grid[i][j]);
                }
            }
        }
        int res = Integer.MAX_VALUE;
        for (int j = 0; j < n; j++) {
            res = Math.min(res, d[n - 1][j]);
        }
        return res;
    }
}

golang 解法, 执行用时: 116 ms, 内存消耗: 6.7 MB, 提交时间: 2023-08-10 09:42:44

func minFallingPathSum(grid [][]int) int {
    n := len(grid)
    d := make([][]int, n)
    for i := 0; i < n; i++ {
        d[i] = make([]int, n)
        for j := 0; j < n; j++ {
            d[i][j] = math.MaxInt
        }
    }
    for i := 0; i < n; i++ {
        d[0][i] = grid[0][i]
    }
    for i := 1; i < n; i++ {
        for j := 0; j < n; j++ {
            for k := 0; k < n; k++ {
                if j == k {
                    continue
                }
                d[i][j] = min(d[i][j], d[i - 1][k] + grid[i][j])
            }
        }
    }
    res := math.MaxInt
    for i := 0; i < n; i++ {
        res = min(res, d[n - 1][i])
    }
    return res
}

func min(a int, b int) int {
    if a < b {
        return a
    }
    return b
}

python3 解法, 执行用时: 9504 ms, 内存消耗: 19.3 MB, 提交时间: 2023-08-10 09:42:15

'''
令状态 f[i][j] 表示从数组 grid 的前 i 行中的每一行选择一个数字，
并且第 i 行选择的数字为 grid[i][j] 时，可以得到的路径和最小值。
f[i][j] 可以从第 i−1 行除了 f[i−1][j] 之外的任意状态转移而来，
因此有如下状态转移方程：
f[i][j] = grid[0][j] # i = 0
f[i][j] = min(f[i-1][k]) + grid[i][j]  # i <> 0, j <> k

最终，我们取第 n−1 行中的最小值，即最小的 min(f[n][j]) 作为答案。
'''
class Solution:
    def minFallingPathSum(self, grid: List[List[int]]) -> int:
        n = len(grid)
        d = [[10**9 for _ in range(n)] for _ in range(n)]
        for i in range(n):
            d[0][i] = grid[0][i]
        for i in range(n):
            for j in range(n):
                for k in range(n):
                    if j == k:
                        continue
                    d[i][j] = min(d[i][j], d[i - 1][k] + grid[i][j])
        return min(d[n - 1])