Shohei Yoshida
Shohei Yoshida's Blog

Follow

Shohei Yoshida's Blog

Follow

LeetCode 931. Minimum Falling Path Sum in F#

Shohei Yoshida's photo
Shohei Yoshida
·Dec 13, 2022·

1 min read

URL

leetcode.com/problems/minimum-falling-path-..

Code

github.com/syohex/dotnet-study/blob/master/..

let minFallingPathSum (matrix: int[,]) : int =
    let rows = Array2D.length1 matrix
    let cols = Array2D.length2 matrix
    let dp = Array2D.create rows cols None

    seq { 0 .. (cols - 1) } |> Seq.iter (fun i -> dp.[0, i] <- Some(matrix.[0, i]))

    for i in 1 .. (rows - 1) do
        for j in 0 .. (cols - 1) do
            if j >= 1 then
                dp.[i, j] <- Some(dp.[i - 1, j - 1].Value + matrix.[i, j])

            if Option.isSome dp.[i, j] then
                dp.[i, j] <- Some(System.Math.Min(dp.[i, j].Value, dp.[i - 1, j].Value + matrix.[i, j]))
            else
                dp.[i, j] <- Some(dp.[i - 1, j].Value + matrix.[i, j])

            if j < cols - 1 then
                dp.[i, j] <- Some(System.Math.Min(dp.[i, j].Value, dp.[i - 1, j + 1].Value + matrix.[i, j]))

    dp.[rows - 1, *] |> Array.map (fun v -> v.Value) |> Array.min
 
Share this