931. Minimum Falling Path Sum

LeetCode medium оригинал: C# #array #csharp #dynamic-programming #leetcode #math #matrix #medium #string

LeetCode Static

Если задан массив целых чисел n x n, верните минимальную сумму любого падающего пути через матрицу. Падающий путь начинается с любого элемента в первой строке и выбирает элемент в следующей строке, который находится либо прямо под ним, либо по диагонали слева/справа. В частности, следующим элементом из позиции (row, col) будет (row + 1, col - 1), (row + 1, col) или (row + 1, col + 1).

Пример:

Input: matrix = [[2,1,3],[6,5,4],[7,8,9]]

Output: 13

C# решение

сопоставлено/оригинал

public class Solution {
    public int MinFallingPathSum(int[][] matrix) {
        int n = matrix.Length;
        int[] dp = (int[])matrix[0].Clone();
        
        for (int i = 1; i < n; i++) {
            int[] newDp = new int[n];
            for (int j = 0; j < n; j++) {
                newDp[j] = matrix[i][j] + Math.Min(dp[j], Math.Min(j > 0 ? dp[j - 1] : int.MaxValue, j < n - 1 ? dp[j + 1] : int.MaxValue));
            }
            dp = newDp;
        }
        
        int minSum = int.MaxValue;
        foreach (int sum in dp) {
            minSum = Math.Min(minSum, sum);
        }
        return minSum;
    }
}

C++ решение

auto-draft, проверить перед отправкой

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

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public int MinFallingPathSum(int[][] matrix) {
        int n = matrix.size();
        vector<int>& dp = (int[])matrix[0].Clone();
        
        for (int i = 1; i < n; i++) {
            vector<int>& newDp = new int[n];
            for (int j = 0; j < n; j++) {
                newDp[j] = matrix[i][j] + min(dp[j], min(j > 0 ? dp[j - 1] : int.MaxValue, j < n - 1 ? dp[j + 1] : int.MaxValue));
            }
            dp = newDp;
        }
        
        int minSum = int.MaxValue;
        foreach (int sum in dp) {
            minSum = min(minSum, sum);
        }
        return minSum;
    }
}

Java решение

сопоставлено/оригинал

class Solution {
    public int minFallingPathSum(int[][] matrix) {
        int n = matrix.length;
        int[] dp = matrix[0].clone();
        
        for (int i = 1; i < n; i++) {
            int[] newDp = new int[n];
            for (int j = 0; j < n; j++) {
                newDp[j] = matrix[i][j] + Math.min(dp[j], Math.min(j > 0 ? dp[j - 1] : Integer.MAX_VALUE, j < n - 1 ? dp[j + 1] : Integer.MAX_VALUE));
            }
            dp = newDp;
        }
        
        int minSum = Integer.MAX_VALUE;
        for (int sum : dp) {
            minSum = Math.min(minSum, sum);
        }
        return minSum;
    }
}

JavaScript решение

сопоставлено/оригинал

var minFallingPathSum = function(matrix) {
    const n = matrix.length;
    let dp = matrix[0].slice();
    
    for (let i = 1; i < n; i++) {
        const newDp = new Array(n).fill(0);
        for (let j = 0; j < n; j++) {
            newDp[j] = matrix[i][j] + Math.min(dp[j], dp[j-1] !== undefined ? dp[j-1] : Infinity, dp[j+1] !== undefined ? dp[j+1] : Infinity);
        }
        dp = newDp;
    }
    
    return Math.min(...dp);
};

Python решение

сопоставлено/оригинал

def minFallingPathSum(matrix):
    n = len(matrix)
    dp = matrix[0][:]
    
    for i in range(1, n):
        new_dp = [0] * n
        for j in range(n):
            new_dp[j] = matrix[i][j] + min(dp[j], dp[j-1] if j > 0 else float('inf'), dp[j+1] if j < n - 1 else float('inf'))
        dp = new_dp
    
    return min(dp)

Go решение

сопоставлено/оригинал

package main

import "math"

func minFallingPathSum(matrix [][]int) int {
    n := len(matrix)
    dp := make([]int, n)
    copy(dp, matrix[0])
    
    for i := 1; i < n; i++ {
        newDp := make([]int, n)
        for j := 0; j < n; j++ {
            minVal := dp[j]
            if j > 0 {
                minVal = int(math.Min(float64(minVal), float64(dp[j-1])))
            }
            if j < n-1 {
                minVal = int(math.Min(float64(minVal), float64(dp[j+1])))
            }
            newDp[j] = matrix[i][j] + minVal
        }
        dp = newDp
    }
    
    minSum := math.MaxInt64
    for _, sum := range dp {
        if sum < minSum {
            minSum = sum
        }
    }
    return minSum
}

Algorithm

Использовать динамическое программирование для хранения минимальных сумм падающих путей для каждой позиции.

Инициализировать dp массив копией первой строки исходной матрицы.

Пройти по каждой строке, обновляя dp массив на основе значений из предыдущей строки.

Вернуть минимальное значение в последней строке dp массива.

😎

Вакансии для этой задачи

Показаны активные вакансии с пересечением по тегам задачи.

Все вакансии

Активных вакансий пока нет.