を使用して動的プログラミングを適用する

動的計画法とは

動的計画法(DP)は再帰の最適解である.再帰関数を使用する場合は、入力値を複数回呼び出して処理することができます.この問題を回避するために、全ての計算結果をテーブル(DPテーブル)に格納してもよい.このようにして、DPテーブルの項目にアクセスすることで入力値の結果を見つけ、再計算する必要はありません.

x番目のFibonacci数を計算するためのDPの使用

この式でx番目のfibonacci数を計算します.

f(0) = 1
f(1) = 1
f(x) = f(x - 1) + f(x - 2)

再帰実装

Python

def fibonacci(x: int) -> int:
    if x < 0:
        raise 'Cannot calculate'

    if x == 0:
        return 1

    if x == 1:
        return 1

    return fibonacci(x - 1) + fibonacci(x - 2)

エリクシール

defmodule Fibonacci do
  def perform(x) when x < 0, do: {:error, "Cannot calculate"}

  def perform(x) do
    {:ok, calculate(x)}
  end

  def calculate(x) do
    IO.inspect("Calculating #{x}")

    case x do
      0 ->
        1

      1 ->
        1

      x ->
        calculate(x - 1) + calculate(x - 2)
    end
  end
end

Xで走らせましょう.

iex(3)> Fibonacci.perform(5)
"Calculating 5"
"Calculating 4"
"Calculating 3"
"Calculating 2"
"Calculating 1"
"Calculating 0"
"Calculating 1"
"Calculating 2"
"Calculating 1"
"Calculating 0"
"Calculating 3"
"Calculating 2"
"Calculating 1"
"Calculating 0"
"Calculating 1"
{:ok, 8}

我々は見ることができるように、我々は最終的な結果を得るために15のステップを取ると、多くの入力値は、複数回再計算されます.以下、各入力値の計算回数を説明する.
入力値
計算時間
0
3
1
5
2
3

DPテーブルの実装

再計算問題を解決するためにdpテーブルを用いてdpを適用できる.
Python

def fibonacci(x: int) -> int:
    if x < 0:
        raise 'Cannot calculate'

    if x == 0:
        return 1

    if x == 1:
        return 1

    dp_table = [0 for _ in range(x + 1)]
    dp_table[0] = 1
    dp_table[1] = 1

    i = 2
    while i <= x:
        dp_table[i] = dp_table[i - 1] + dp_table[i - 2]
        i += 1

    return dp_table[x]

あるいは、DPテーブルをビルドするためにdictを使うことができます.

def fibonacci(x: int) -> int:
    if x < 0:
        raise 'Cannot calculate'

    if x == 0:
        return 1

    if x == 1:
        return 1

    dp_table = {0: 1, 1: 1}

    i = 2
    while i <= x:
        dp_table[i] = dp_table[i - 1] + dp_table[i - 2]
        i += 1

    return dp_table[x]

エリクシール

defmodule Fibonacci do
  def perform(x) when x < 0, do: {:error, "Cannot calculate"}

  def perform(x) do
    {:ok, calculate(x, 0)}
  end

  defp calculate(x, index, table \\ %{}) do
    IO.inspect("Calculating #{index}")

    fibonacci_value =
      case index do
        0 ->
          1

        1 ->
          1

        index ->
          table[index - 1] + table[index - 2]
      end

    if index == x do
      fibonacci_value
    else
      table = Map.put(table, index, fibonacci_value)
      calculate(x, index + 1, table)
    end
  end
end

Xで走らせましょう.

iex(3)> Fibonacci.perform(5)
"Calculating 0"
"Calculating 1"
"Calculating 2"
"Calculating 3"
"Calculating 4"
"Calculating 5"
{:ok, 8}

我々は見ることができるように、計算のためのすべての入力値が一度訪れ、我々は最終的な結果を得るためにわずか5歩かかる.
また、Enum.reduce/3機能を備えたアプローチもあります.

defmodule Fibonacci do
  def perform(x) when x < 0, do: {:error, "Cannot calculate"}

  def perform(0), do: {:ok, 1}

  def perform(1), do: {:ok, 1}

  def perform(x) do
    dp_table =
      Enum.reduce(2..x, %{0 => 1, 1 => 1}, fn index, acc ->
        Map.put(acc, index, acc[index - 1] + acc[index - 2])
      end)

    {:ok, dp_table[x]}
  end
end

2変数のみの実装

場合によっては、すべての計算されたFibonacci番号を格納する必要はありません.実際には、( x - 1 )- thと( x - 2 )番目の数字を気にします.DPテーブルのためのスペースを減らすために、計算された値をキャッシュするために、2つの変数だけを使用できます.

Close 2 :(x - 2)フィボナッチ数を表します.

Crest 1 :(x - 1)フィボナッチ数を表します.

defmodule Fibonacci do
  def perform(x) when x < 0, do: {:error, "Cannot calculate"}

  def perform(0), do: {:ok, 1}

  def perform(1), do: {:ok, 1}

  def perform(x) do
    {:ok, calculate(x, 2, 1, 1)}
  end

  defp calculate(x, index, c_1, c_2) do
    fibonacci_value = c_1 + c_2

    if index == x do
      fibonacci_value
    else
      calculate(x, index + 1, fibonacci_value, c_1)
    end
  end
end

結論

dpを用いたx番目fifiacci数計算法を紹介した.DPを使用すると、アプリケーションを高速にDPテーブルで計算時間を節約することによって実行することができます.次の記事では、Elixirで他のDP問題を解決する方法を紹介します.