动静布局

最近在猛刷动静布局题，正好 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  endend

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