Dynamic Programming Algorithms - 1 - Fibonacci Numbers
Dynamic programming allows for more efficient implantation of divide and conquer algorithms.
Fibonacci Numbers
This is the definition for the Fibonacci numbers:
\[F(n)=\begin{cases} 1 & \text{if } n=0\text{ or } 1\\ F(n-1)+F(n-2) & \text{if } n> 1 \end{cases}\]and the code that we had before:
Algorithm F(n)
if n == 0 OR n == 1 then
return 1
else
return F(n - 1) + F(n - 2)
This code calculates particular Fibonacci numbers many times which is inefficient.
Memorisation
To improve on this we can memorise new Fibonacci numbers so that we don’t have to calculate them again:
- Store $F(n)$ somewhere after we have computed its value.
- Afterwards, we don’t need to re-compute $F(n)$ as we can retrieve its value from the memory.
Main Algorithm
set v[0] = 1
set v[1] = 1
for i = 2 to n do
v[i] = -1 // initialise all other values to -1
output F(n)
Algorithm F(n)
if v[n] < 0 then
v[n] = F(n - 1) + F(n - 2)
return v[n]
This significantly reduces the amount of calculation.
Compute $F(n)$ in Advance
The 2$^{nd}$ version still makes many function calls. Making many function calls negatively effects performance. To improve this we can compute the values from the bottom-up.
Algorithm F(n)
set v[0] = 1
set v[1] = 1
for i = 2 to n do
v[i] = v[i - 1] + v[v - 2]
return v[n]
Summary
- Write down a formula that relates a solution of a problem with those of sub-problems:
- $F(n)=F(n-1)+F(n-2)$
- Index the sub-problems so that they can be stored and retrieved easily in a table.
- Fill the table in some bottom-up manner:
- Start filling the solution of the smallest problem.
- This ensures that when we solve a particular sub-problem, the solutions of all smaller sub-problems on which it depends are available.