算法每日一练 (22)

💢欢迎来到张翊尘的技术站
💥技术如江河，汇聚众志成。代码似星辰，照亮行征程。开源精神长，传承永不忘。携手共前行，未来更辉煌💥

官方站点： 力扣 Leetcode

算法每日一练 (22)

下降路径最小和

题目地址：下降路径最小和

题目描述

给你一个 n x n 的 方形 整数数组 matrix ，请你找出并返回通过 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
解释：如图所示，为和最小的两条下降路径

示例 2：

输入：matrix = [[-19,57],[-40,-5]]
输出：-59
解释：如图所示，为和最小的下降路径

提示：

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

解题思路

• 首先处理边界条件，当 n == 1 时，直接返回 matrix[0][0] 即可。

• dp 数组初始化为矩阵的最后一行，表示到达最后一行每个位置的最小路径和。

• 从倒数第二行开始，逐行向上计算。对于每一行的每个位置 j，计算从该位置到下一行的最小路径和。

• 在循环中，使用一个临时数组 t 来存储当前行的计算结果，避免直接修改 dp 数组。

  • 当 j = 0 时，只能从前一行的 j 或 j+1 中选择。
  • 当 j = n−1 时，只能从前一行的 j−1 或 j 中选择。
  • 当 j > 0 并且 j < n-1 时，满足下面状态转移方程：

  $$dp[j]=matrix[i][j]+min(dp[j-1],dp[j],dp[j+1])$$

  对于每个位置 (i,j)，可以从前一行的相邻三个位置 (i+1,j−1)、(i+1,j)、(i+1,j+1) 中选择一个最小值。

• 每次计算完一行后，将临时数组 t 赋值给 dp，以便下一次迭代使用。

• 最终，dp 数组中的最小值即为从第一行到最后一行的最小下降路径和。

lua 和 golang 采用的解法是上述解题思路的方式。

c/c++ 的解法是直接在原有的 matrix 矩阵中修改，并且无需借助临时数组 t，感兴趣的小伙伴可以参考该解法。

解题代码

c/c++

class Solution {
public:
    int minFallingPathSum(vector<vector<int>>& matrix) {
        int n = matrix.size();
        if (n == 1)
            return matrix[0][0];

        for (int i = n - 2; i >= 0; i--) {
            for (int j = 0; j < n; j++) {
                int minVal = matrix[i + 1][j];
                if (j > 0)
                    minVal = std::min(minVal, matrix[i + 1][j - 1]);

                if (j < n - 1)
                    minVal = std::min(minVal, matrix[i + 1][j + 1]);

                matrix[i][j] += minVal;
            }
        }

        int minVal = matrix[0][0];
        for (int i = 1; i < n; i++)
            minVal = std::min(matrix[0][i], minVal);

        return minVal;
    }
};

golang

func minFallingPathSum(matrix [][]int) int {
	n := len(matrix)
	if n == 1 {
		return matrix[0][0]
	}

	dp := make([]int, n)
	for i := 0; i < n; i++ {
		dp[i] = matrix[n-1][i]
	}

	for i := n - 2; i >= 0; i-- {
		t := make([]int, n)
		for j := 0; j < n; j++ {
			if j == 0 {
				t[0] = matrix[i][0] + min(dp[0], dp[1])
			} else if j == n-1 {
				t[n-1] = matrix[i][j] + min(dp[n-1], dp[n-2])
			} else {
				t[j] = matrix[i][j] + min(min(dp[j], dp[j-1]), dp[j+1])
			}
		}

		dp = t
	}

	minVal := dp[0]
	for i := 1; i < len(dp); i++ {
		minVal = min(minVal, dp[i])
	}
	return minVal
}

lua

local function minFallingPathSum(matrix)
    local n = #matrix
    if n == 1 then
        return matrix[1][1]
    end

    local dp = {}
    for i = 1, #matrix do
        dp[i] = matrix[n][i]
    end

    for i = n - 1, 1, -1 do
        local t = {}
        for j = 1, n do
            if j == 1 then
                t[1] = matrix[i][1] + math.min(dp[1], dp[2])
            elseif j == n then
                t[n] = matrix[i][j] + math.min(dp[n - 1], dp[n])
            else
                t[j] = matrix[i][j] + math.min(math.min(dp[j], dp[j - 1]), dp[j + 1])
            end
        end
        dp = t
    end

    local minVal = dp[1]
    for i = 2, #dp do
        minVal = math.min(dp[i], minVal)
    end

    return minVal
end

🌺🌺🌺撒花！

如果本文对你有帮助，就点关注或者留个👍
如果您有任何技术问题或者需要更多其他的内容，请随时向我提问。