What is dynamic programing?
Dynamic programing (DP) is an optimization solution for recursion. When using a recursive function, it may be call and processed with an input value multiple times. To prevent this problem, we may store all calculated results in a table (the DP table). By this way, we just find the result of an input value by accessing an item in DP table and don't need to re-calculate it.
Using DP to calculate the x-th Fibonacci number
The x-th fibonacci number is calculated by this formula:
f(0) = 1
f(1) = 1
f(x) = f(x - 1) + f(x - 2)
Implementation with recursion
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)
Elixir
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
Let's run with x is 5:
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}
As we can see, we take 15 steps to get the final result, and a lot of input values are re-calculated multiple times. This table explains number of calculating times of each input value:
| input value | calculating times |
|---|---|
| 0 | 3 |
| 1 | 5 |
| 2 | 3 |
Implementation with DP table
To solve re-calculation problem, we can apply DP by using DP table.
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]
Or we can use a dict to build the DP table:
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]
Elixir
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
Let's run with x is 5:
iex(3)> Fibonacci.perform(5)
"Calculating 0"
"Calculating 1"
"Calculating 2"
"Calculating 3"
"Calculating 4"
"Calculating 5"
{:ok, 8}
As we can see, all input values for calculating are visited once, and we take only 5 steps to get the final result.
We also have an approach with Enum.reduce/3 function:
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
Implementation with only 2 variables
In some case, we don't need to store all calculated Fibonacci numbers. In fact, we just care the (x - 1)-th and (x - 2)-th numbers. To reduce space for DP table, we can use only 2 variables to cache calculated values:
- c_2: represent the (x - 2)-th Fibonacci number.
- c_1: represent the (x - 1)-th Fibonacci number.
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
Conclusion
This article introduces approaches to calculate x-th Fibonacci number using DP. With DP, we can make the application running faster by saving calculating times with DP table. In next articles, I will introduce approaches to solve other DP problems with Elixir.
Top comments (0)