Shohei Yoshida
Shohei Yoshida's Blog

Shohei Yoshida's Blog

LeetCode 871. Minimum Number of Refueling Stops in F#

Shohei Yoshida's photo
Shohei Yoshida
·Aug 20, 2022·

1 min read

URL

leetcode.com/problems/minimum-number-of-ref..

Code

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

let minRefuelStops (target: int) (startFuel: int) (stations: (int * int) []) : int =
    let len = stations.Length
    let dp = Array.zeroCreate (len + 1)
    dp.[0] <- startFuel

    for i in 0 .. (len - 1) do
        for j in seq { 0..i } |> Seq.rev do
            if dp.[j] >= fst stations.[i] then
                dp.[j + 1] <- System.Math.Max(dp.[j + 1], dp.[j] + (snd stations.[i]))

    match dp
          |> Array.mapi (fun i v -> i, v)
          |> Array.tryFind (fun (_, v) -> v >= target)
        with
    | None -> -1
    | Some ((i, _)) -> i
 
Share this