931. 下降路径最小和

题目描述

输入一个 n x n 的整数矩阵 matrix。

下降路径从第一行的任意一格出发，每次走到下一行，直到最后一行，每行恰好选一格。若当前在 (row, col)，下一步只能到 (row + 1, col - 1)、(row + 1, col) 或 (row + 1, col + 1) 中位于矩阵内的格子。

路径和是路径上所有格子的值之和。返回所有下降路径中路径和的最小值。

示例 1

输入：matrix = [[2,1,3],[6,5,4],[7,8,9]]
输出：13

解释：例如 1 -> 5 -> 7 或 1 -> 4 -> 8，和都是 13。

示例 2

输入：matrix = [[-19,57],[-40,-5]]
输出：-59

解释：走 -19 -> -40，和为 -59。

数据范围

n == matrix.length == matrix[i].length
1 <= n <= 100
-100 <= matrix[i][j] <= 100

解题思路：滚动数组动态规划

设 dp[j] 为到达当前行第 j 列的最小路径和。下一行的格子 (i,j) 只能从上一行的 j-1、j、j+1 三列过来，所以 nxt[j] = min(dp[j-1], dp[j], dp[j+1]) + matrix[i][j]（越界的列不参与）。逐行推到最后，答案是最后一行 dp 的最小值。

为什么正确

处理完第 i 行后，dp[j] 等于从第 0 行任意位置到 (i,j) 的所有合法路径中的最小和。

复杂度分析

时间 O(n²)，空间 O(n)。

易错点

不能在 dp 上原地从左到右更新：算 nxt[j+1] 时要用上一行的 dp[j]，原地覆盖后就是当前行的值了。用新数组 nxt，或一次性保存旧值。第一列和最后一列只有两个来源。

参考代码

Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。

class Solution:
    def minFallingPathSum(self, matrix: List[List[int]]) -> int:
        n = len(matrix)
        dp = matrix[0][:]
        for i in range(1, n):
            nxt = [0] * n
            for j in range(n):
                best = dp[j]
                if j > 0:
                    best = min(best, dp[j - 1])
                if j < n - 1:
                    best = min(best, dp[j + 1])
                nxt[j] = best + matrix[i][j]
            dp = nxt
        return min(dp)

class Solution {
    public int minFallingPathSum(int[][] matrix) {
        int n = matrix.length;
        int[] dp = matrix[0].clone();
        for (int i = 1; i < n; i++) {
            int[] nxt = new int[n];
            for (int j = 0; j < n; j++) {
                int best = dp[j];
                if (j > 0) {
                    best = Math.min(best, dp[j - 1]);
                }
                if (j < n - 1) {
                    best = Math.min(best, dp[j + 1]);
                }
                nxt[j] = best + matrix[i][j];
            }
            dp = nxt;
        }
        int ans = dp[0];
        for (int v : dp) ans = Math.min(ans, v);
        return ans;
    }
}

class Solution {
public:
    int minFallingPathSum(vector<vector<int>>& matrix) {
        int n = matrix.size();
        vector<int> dp = matrix[0];
        for (int i = 1; i < n; i++) {
            vector<int> nxt(n, 0);
            for (int j = 0; j < n; j++) {
                int best = dp[j];
                if (j > 0) {
                    best = min(best, dp[j - 1]);
                }
                if (j < n - 1) {
                    best = min(best, dp[j + 1]);
                }
                nxt[j] = best + matrix[i][j];
            }
            dp = nxt;
        }
        return *min_element(dp.begin(), dp.end());
    }
};

func minFallingPathSum(matrix [][]int) int {
	n := len(matrix)
	dp := append([]int{}, matrix[0]...)
	for i := 1; i < n; i++ {
		nxt := make([]int, n)
		for j := 0; j < n; j++ {
			best := dp[j]
			if j > 0 {
				best = min(best, dp[j-1])
			}
			if j < n-1 {
				best = min(best, dp[j+1])
			}
			nxt[j] = best + matrix[i][j]
		}
		dp = nxt
	}
	ans := dp[0]
	for _, v := range dp {
		ans = min(ans, v)
	}
	return ans
}

var minFallingPathSum = function(matrix) {
    const n = matrix.length;
    let dp = matrix[0].slice();
    for (let i = 1; i < n; i++) {
        const nxt = new Array(n).fill(0);
        for (let j = 0; j < n; j++) {
            let best = dp[j];
            if (j > 0) {
                best = Math.min(best, dp[j - 1]);
            }
            if (j < n - 1) {
                best = Math.min(best, dp[j + 1]);
            }
            nxt[j] = best + matrix[i][j];
        }
        dp = nxt;
    }
    return Math.min(...dp);
};

function minFallingPathSum(matrix: number[][]): number {
    const n = matrix.length;
    let dp = matrix[0].slice();
    for (let i = 1; i < n; i++) {
        const nxt = new Array(n).fill(0);
        for (let j = 0; j < n; j++) {
            let best = dp[j];
            if (j > 0) {
                best = Math.min(best, dp[j - 1]);
            }
            if (j < n - 1) {
                best = Math.min(best, dp[j + 1]);
            }
            nxt[j] = best + matrix[i][j];
        }
        dp = nxt;
    }
    return Math.min(...dp);
}

载入编辑器，自己跑一遍 →

其他解法

记忆化搜索是自顶向下、主解法是自底向上，两者时间都是 O(n²)；滚动数组把空间压到 O(n)。

解法 2：记忆化搜索时间 O(n²)，空间 O(n²)

定义 dfs(i, j) 为从 (i, j) 出发向下走到最后一行的最小路径和。最后一行直接返回 matrix[i][j]。否则取下一行 j - 1、j、j + 1 三个位置中的最小值再加上 matrix[i][j]，结果存入备忘录。答案是第一行所有 dfs(0, j) 的最小值。

自顶向下的写法和状态定义一一对应，容易从递归思路推出。需要 O(n²) 备忘录和 O(n) 递归栈，空间比滚动数组大。

from functools import lru_cache

class Solution:
    def minFallingPathSum(self, matrix: List[List[int]]) -> int:
        n = len(matrix)

        @lru_cache(maxsize=None)
        def dfs(i, j):
            if i == n - 1:
                return matrix[i][j]
            best = dfs(i + 1, j)
            if j > 0:
                best = min(best, dfs(i + 1, j - 1))
            if j < n - 1:
                best = min(best, dfs(i + 1, j + 1))
            return matrix[i][j] + best

        return min(dfs(0, j) for j in range(n))

class Solution {
    int n;
    int[][] memo;
    boolean[][] seen;

    int dfs(int[][] matrix, int i, int j) {
        if (i == n - 1) return matrix[i][j];
        if (seen[i][j]) return memo[i][j];
        int best = dfs(matrix, i + 1, j);
        if (j > 0) best = Math.min(best, dfs(matrix, i + 1, j - 1));
        if (j < n - 1) best = Math.min(best, dfs(matrix, i + 1, j + 1));
        seen[i][j] = true;
        return memo[i][j] = matrix[i][j] + best;
    }

    public int minFallingPathSum(int[][] matrix) {
        n = matrix.length;
        memo = new int[n][n];
        seen = new boolean[n][n];
        int ans = Integer.MAX_VALUE;
        for (int j = 0; j < n; j++) ans = Math.min(ans, dfs(matrix, 0, j));
        return ans;
    }
}

class Solution {
public:
    int n;
    vector<vector<int>> memo;
    vector<vector<bool>> seen;

    int dfs(vector<vector<int>>& matrix, int i, int j) {
        if (i == n - 1) return matrix[i][j];
        if (seen[i][j]) return memo[i][j];
        int best = dfs(matrix, i + 1, j);
        if (j > 0) best = min(best, dfs(matrix, i + 1, j - 1));
        if (j < n - 1) best = min(best, dfs(matrix, i + 1, j + 1));
        seen[i][j] = true;
        return memo[i][j] = matrix[i][j] + best;
    }

    int minFallingPathSum(vector<vector<int>>& matrix) {
        n = matrix.size();
        memo.assign(n, vector<int>(n, 0));
        seen.assign(n, vector<bool>(n, false));
        int ans = INT_MAX;
        for (int j = 0; j < n; j++) ans = min(ans, dfs(matrix, 0, j));
        return ans;
    }
};

func minFallingPathSum(matrix [][]int) int {
	n := len(matrix)
	memo := make([][]int, n)
	seen := make([][]bool, n)
	for i := range memo {
		memo[i] = make([]int, n)
		seen[i] = make([]bool, n)
	}
	var dfs func(i, j int) int
	dfs = func(i, j int) int {
		if i == n-1 {
			return matrix[i][j]
		}
		if seen[i][j] {
			return memo[i][j]
		}
		best := dfs(i+1, j)
		if j > 0 {
			best = min(best, dfs(i+1, j-1))
		}
		if j < n-1 {
			best = min(best, dfs(i+1, j+1))
		}
		seen[i][j] = true
		memo[i][j] = matrix[i][j] + best
		return memo[i][j]
	}
	ans := math.MaxInt32
	for j := 0; j < n; j++ {
		ans = min(ans, dfs(0, j))
	}
	return ans
}

var minFallingPathSum = function(matrix) {
    const n = matrix.length;
    const memo = Array.from({length: n}, () => new Array(n).fill(null));
    const dfs = (i, j) => {
        if (i === n - 1) return matrix[i][j];
        if (memo[i][j] !== null) return memo[i][j];
        let best = dfs(i + 1, j);
        if (j > 0) best = Math.min(best, dfs(i + 1, j - 1));
        if (j < n - 1) best = Math.min(best, dfs(i + 1, j + 1));
        return memo[i][j] = matrix[i][j] + best;
    };
    let ans = Infinity;
    for (let j = 0; j < n; j++) ans = Math.min(ans, dfs(0, j));
    return ans;
};

function minFallingPathSum(matrix: number[][]): number {
    const n = matrix.length;
    const memo: (number | null)[][] = Array.from({length: n}, () => new Array(n).fill(null));
    const dfs = (i: number, j: number): number => {
        if (i === n - 1) return matrix[i][j];
        if (memo[i][j] !== null) return memo[i][j] as number;
        let best = dfs(i + 1, j);
        if (j > 0) best = Math.min(best, dfs(i + 1, j - 1));
        if (j < n - 1) best = Math.min(best, dfs(i + 1, j + 1));
        memo[i][j] = matrix[i][j] + best;
        return memo[i][j] as number;
    };
    let ans = Infinity;
    for (let j = 0; j < n; j++) ans = Math.min(ans, dfs(0, j));
    return ans;
}

动态规划专题的其他题目

查看动态规划全部题目 →