首頁 解題筆記 Leetcode Medium

⭐️⭐️⭐️

# 題目敘述

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;
    }
};


單字
** **
!! !!
片語 & 搭配詞
!! !!