931. Minimum Falling Path Sum

⭐⭐⭐

題目敘述

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

Example 1

Input: matrix = [[2,1,3],[6,5,4],[7,8,9]] Output: 13 Explanation: There are two falling paths with a minimum sum as shown.

Example 2

Input: matrix = [[-19,57],[-40,-5]] Output: -59 Explanation: The falling path with a minimum sum is shown.

解題思路

Solution

class Solution {
    public int minFallingPathSum(int[][] matrix) {
        int size = matrix.length;
        int min = Integer.MAX_VALUE;

        for (int i = 1; i < size; i++) {
            for (int j = 0; j < size; j++) {
                min = matrix[i - 1][j];
                if (j > 0) {
                    min = Math.min(matrix[i - 1][j - 1], min);
                }
                if (j < size - 1) {
                    min = Math.min(matrix[i - 1][j + 1], min);
                }
                matrix[i][j] = matrix[i][j] + min;
            }
        }

        min = Integer.MAX_VALUE;

        for (int i = 0; i < size; i++) {
            if (min > matrix[size - 1][i]) {
                min = matrix[size - 1][i];
            }
        }

        return min;
    }
}

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int minFallingPathSum(vector<vector<int>>& matrix) {
        int size = matrix.size();
        int ans = INT_MAX;

        for (int i = 1; i < size; i++) {
            for (int j = 0; j < size; j++) {
                ans = matrix[i - 1][j];
                if (j > 0) {
                    ans = min(matrix[i - 1][j - 1], ans);
                }
                if (j < size - 1) {
                    ans = min(matrix[i - 1][j + 1], ans);
                }
                matrix[i][j] = matrix[i][j] + ans;
            }
        }

        ans = INT_MAX;

        for (int i = 0; i < size; i++) {
            if (ans > matrix[size - 1][i]) {
                ans = matrix[size - 1][i];
            }
        }

        return ans;
    }
};