我正在尝试处理二维列表中的数据。我知道所有对象都是不可变的。我的递归调用正在回溯，状态正在消失。当你没有状态时，处理这个问题的标准方法是什么？
defmodule Euler do
def euler_15() do
grid = create_2d_list(10, 10)
# write out 1's to the first row
grid = write_out_first_row(grid, 0)
grid = write_out_first_column(grid, 0)
fill_out_remainder(grid, 1, 1)
end
def fill_out_remainder(grid, 10, _) do
IO.puts("finale to fill_out_remainder")
end
def write_out_column(grid, row, 10) do
IO.puts("finale! to write out column is running for row: #{row}")
end
def write_out_column(grid, row, col) do
IO.puts("*** write out column is running for column: #{col} and row: #{row}")
IO.puts("Reading from this grid state")
IO.inspect(grid)
cell_above = get_element(grid, row-1, col)
IO.puts("value from column above is: #{cell_above}")
cell_left = get_element(grid, row, col-1)
IO.puts("value from left cell is: #{cell_left}")
grid = set_element(grid,row,col,cell_above+cell_left)
IO.inspect(grid)
write_out_column(grid, row, col+1)
end
def write_out_row(grid, row) do
write_out_column(grid, row, 1)
end
def fill_out_remainder(grid, row_ct, col_ct) do
write_out_row(grid, row_ct)
fill_out_remainder(grid, row_ct + 1, col_ct)
end
def write_out_first_row(grid, 10) do
grid
end
def write_out_first_row(grid, counter) do
grid = set_element(grid, 0, counter, 1)
write_out_first_row(grid, counter + 1)
end
def write_out_first_column(grid, 10) do
grid
end
def write_out_first_column(grid, counter) do
grid = set_element(grid, counter, 0, 1)
write_out_first_column(grid, counter + 1)
end
def create_2d_list(rows, cols) do
for _ <- 1..rows, do: for(_ <- 1..cols, do: nil)
end
def get_element(grid, r, c) do
# first step - extract the row
the_row = Enum.at(grid, r)
# now get the value
Enum.at(the_row,c)
end
def set_element(grid, r, c, new_value) do
# stage 1 - extract the row
the_row = Enum.at(grid, r)
# stage 2 - update the row
the_row = List.replace_at(the_row, c, new_value)
# stage 3 - update the 2d lists row to be changed
# with the updated row
grid = List.replace_at(grid, r, the_row)
grid
end
end
Euler.euler_15()
Euler 15 是一个典型的动态规划问题。这是我的方法。 （所有指数均从 1 开始）
“标准”方法是进行递归调用 将状态与所有其他参数一起获取， 并返回该递归的结果 以及更新后的状态。
defmodule Euler do
def euler_15(rows, cols) do
# The first arg is the "state",
# which I prefer to call it "memo".
{routes, _memo} = solve(%{}, rows, cols, 1, 1)
routes
end
# The recursive function should return
# both the number of routes
# and the updated memo.
defp solve(memo, rows, _cols, rows, _j), do: {1, memo}
defp solve(memo, _rows, cols, _i, cols), do: {1, memo}
defp solve(memo, rows, cols, i, j) do
case memo[{i, j}] do
nil ->
{right, memo} = solve(memo, rows, cols, i, j + 1)
{down, memo} = solve(memo, rows, cols, i + 1, j)
routes = right + down
memo = Map.put(memo, {i, j}, routes)
{routes, memo}
routes ->
{routes, memo}
end
end
end
这是我通过恢复可变性来解决记忆问题的方法。这比 V1 更容易编码并且运行速度更快。
defmodule Euler do
def euler_15(rows, cols) do
# Because we are going to use process dictionary as the memo,
# and we don't want to pollute the process dictionary of the caller,
# we just spawn a child process to do all the nasty work.
Task.async(fn ->
solve(rows, cols, 1, 1)
end)
|> Task.await()
end
# The process dictionary is the memo,
# so we don't need to pass in the memo any more.
# We don't need to return the memo, either.
defp solve(rows, _cols, rows, _j), do: 1
defp solve(_rows, cols, _i, cols), do: 1
defp solve(rows, cols, i, j) do
memoized({i, j}, fn ->
right = solve(rows, cols, i, j + 1)
down = solve(rows, cols, i + 1, j)
right + down
end)
end
defp memoized(key, fun) do
case Process.get(key) do
nil ->
val = fun.()
Process.put(key, val)
val
val ->
val
end
end
end
您仍然需要跟踪更新的备忘录。
defmodule Euler do
def euler_15(rows, cols) do
memo = for i <- 1..rows, into: %{} do
{{i, 1}, 1}
end
memo = for j <- 1..cols, into: memo do
{{1, j}, 1}
end
memo = for i <- 2..rows, j <- 2..cols, reduce: memo do
memo -> Map.put(memo, {i, j}, memo[{i - 1, j}] + memo[{i, j - 1}])
end
memo[{rows, cols}]
end
end