动静布局

最近在猛刷动静布局题，正好 leetcode 中国有“学习打算”的性能，每天给我调配几道题的工作。

总结出了一套做动静布局的小模板。以“跳跃游戏”这道题为例

defmodule Solution do
  @spec can_jump(nums :: [integer]) :: boolean
  def can_jump([x]), do: true
  def can_jump([h | _] = nums) do

    # 首先结构初始状态，因为 List 的拜访工夫是 O(n) 的，咱们先将其转换为 Map
    state = %{0 => h, nums: nums |> Enum.with_index() |> Enum.into(%{}, fn {v, k} -> {k, v} end)}

    # 用一个 Agent 来保留状态，因为 elixir 外面个别不应用全局变量
    Agent.start(fn -> state end, name: __MODULE__)

    r = dp(length(nums) - 1)

    # 完结后须要进行 Agent，否则状态会保留到下一个测试
    Agent.stop(__MODULE__)
    !!r
  end

  # dp 主逻辑
  defp dp(i) do
    find_and_store(i, fn %{nums: nums} -> nums[i] end, fn step -> 
      case dp(i - 1) do
        false -> false
        j ->
          if j >= i do
            max(j, i + step)
          else
            false
          end
      end
    end)
  end

  # 通用函数，计算并存储最新状态。fget 函数是在 Agent 里执行，再返回后果。# fdp 是状态转换的函数，其输出是 fget 的后果。defp find_and_store(i, fget, fdp) do
    case Agent.get(__MODULE__, fn m -> m[i] end) do
      nil -> 
        x = Agent.get(__MODULE__, fget) |> fdp.()
        Agent.update(__MODULE__, fn m -> Map.put(m, i, x) end)
        x

      x ->
        x
    end
  end
end

大家可能会说，你这样乱递归，不会爆栈吗？其实我也是战战兢兢的，惟恐不必尾递归会导致爆栈，但目前还没有遇到这种状况。可能是 beam 的优化很好吧。