931.下降路径最小和

链接：931.下降路径最小和
难度：Medium
标签：数组、动态规划、矩阵
简介：给你一个 n x n 的 方形 整数数组 matrix ，请你找出并返回通过 matrix 的下降路径 的 最小和 。

题解 1 - python

• 编辑时间：2023-07-13
• 执行用时：80ms
• 内存消耗：17MB
• 编程语言：python
• 解法介绍：同上。

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

题解 2 - rust

• 编辑时间：2023-07-13
• 执行用时：4ms
• 内存消耗：2.1MB
• 编程语言：rust
• 解法介绍：同上。

impl Solution {
    pub fn min_falling_path_sum(mut matrix: Vec<Vec<i32>>) -> i32 {
        let n = matrix.len();
        for i in 1..n {
            for j in 0..n {
                let mut val = matrix[i][j] + matrix[i - 1][j];
                if j > 0 {
                    val = val.min(matrix[i][j] + matrix[i - 1][j - 1]);
                }
                if j < n - 1 {
                    val = val.min(matrix[i][j] + matrix[i - 1][j + 1]);
                }
                matrix[i][j] = val;
            }
        }
        *matrix[n - 1].iter().min().unwrap()
    }
}

题解 3 - cpp

• 编辑时间：2023-07-13
• 执行用时：12ms
• 内存消耗：9.9MB
• 编程语言：cpp
• 解法介绍：遍历。

class Solution {
public:
    int minFallingPathSum(vector<vector<int>>& matrix) {
        int n = matrix.size(), res = INT_MAX;
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < n; j++) {
                int val = matrix[i][j] + matrix[i - 1][j];
                if (j > 0) val = min(val, matrix[i][j] + matrix[i - 1][j - 1]);
                if (j < n - 1) val = min(val, matrix[i][j] + matrix[i - 1][j + 1]);
                matrix[i][j] = val;
            }
        }
        for (int j = 0; j < n; j++) res = min(res, matrix[n - 1][j]);
        return res;
    }
};