931. Minimum Falling Path Sum

leetcode medium

#array#csharp#dynamic-programming#leetcode#math#matrix#medium#string

Task

Если задан массив целых чисел 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# solution

matched/original

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++ solution

auto-draft, review before submit

#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 solution

matched/original

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 solution

matched/original

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 solution

matched/original

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 solution

matched/original

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
}

Explanation

Algorithm

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

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

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

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

😎