URL

leetcode.com/problems/longest-increasing-pa..

Code

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

open System

let longestIncreasingPath (matrix: int [,]) : int =
    let steps = [ (-1, 0); (0, -1); (1, 0); (0, 1) ]

    let rows = Array2D.length1 matrix
    let cols = Array2D.length2 matrix

    let validNextPositions row col (matrix: int [,]) =
        steps
        |> List.map (fun (r, c) -> row + r, col + c)
        |> List.filter (fun (r, c) ->
            r >= 0
            && r < rows
            && c >= 0
            && c < cols
            && matrix.[r, c] > matrix.[row, col])

    let rec longestIncreasingPath' row col matrix (cache: Map<(int * int), int>) =
        match Map.tryFind (row, col) cache with
        | Some (v) -> v, cache
        | None ->
            let ret, cache' =
                validNextPositions row col matrix
                |> List.fold
                    (fun (ret, cache) (r, c) ->
                        let r, cache' = longestIncreasingPath' r c matrix cache
                        Math.Max(r, ret), cache')
                    (0, cache)

            ret + 1, Map.add (row, col) (ret + 1) cache'

    let points =
        seq {
            for i in 0 .. (rows - 1) do
                for j in 0 .. (cols - 1) do
                    yield (i, j)
        }

    points
    |> Seq.fold
        (fun (acc, cache) (r, c) ->
            let ret, cache' = longestIncreasingPath' r c matrix cache
            Math.Max(acc, ret), cache')
        (0, Map.empty)
    |> fst