URL

https://leetcode.com/problems/2-keys-keyboard/description/?envType=daily-question&envId=2024-08-19

Code

https://github.com/syohex/dotnet-study/tree/master/fsharp/leetcode/challenge/202408/2_keys_keyboard/main.fsx

let minSteps (n: int) : int =
    let rec minSteps' len pasteSize n cache =
        if len = n then
            0, cache
        elif len > n then
            1001, cache
        else
            match Map.tryFind (len, pasteSize) cache with
            | Some(v) -> v, cache
            | None ->
                let ret1, cache = minSteps' (len + pasteSize) pasteSize n cache
                let ret2, cache = minSteps' (len * 2) len n cache
                let ret = min (ret1 + 1) (ret2 + 2)
                ret, Map.add (len, pasteSize) ret cache

    if n = 1 then 0 else 1 + (minSteps' 1 1 n Map.empty |> fst)