Dynamic programming is both a mathematical optimization method and a computer programming method. The method was developed by Richard Bellman in the 1950s and has found applications in numerous fields, from aerospace engineering to economics. Today we learn 5 concrete steps of Dynamic Programming.
To achieve this we will use Fibonacci Sequence. The sequence was discovered by Fibonacci, first appears in the book Liber Abaci (The Book of Calculation, 1202) by Fibonacci where it is used to calculate the growth of rabbit populations.
Visualize the problem
The sequence is given by,
The pattern is naive, every number is the sum of the previous two, where starting two numbers are 0 and 1. We can visualize it by,
Find a suitable subproblem
To find any number, we must know its previous two. Like the 6th Fibonacci number is the sum of the previous two which are 4th and 5th. Means 3+5=8. To find the nth number in the sequence we must know the (n-1)th and (n-2)th.
Find the relationship amongst subproblems
For those (n-1)th and (n-2)th Fibonacci number we must know the previous two of each of them.
Generalize the relationship
Now We can easily generate a functional equation generalizing our problem, if F_n is the nth Fibonacci sequence then,
Implement by solving subproblems in order
For this, we will use recursion,
Another valid implementation will be,
Dynamic Programming is a very powerful mathematical used in every field of science. The generalized way to solve problems dynamically, first to visualize the problem. After that find the appropriate subproblems. Find relation among the subproblems and generalized over the spectrum of n. In the last implement it by solving subproblems.
A tree without branches is very easy to climb because there is only one potential way up. There is a programming technique named branchless programming, which provides a better and efficient solution to problems.
Data Science has a variety of sorting algorithms but the five most basic are here.