5 steps closer towards Dynamic Programming

A plot of Lorenz’s strange attractor | design of a Dynamic System

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 appearing 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 numbers 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,

Output:

8

Another valid implementation will be,

Output:

8

Conclusion

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.

Check out my GitHub and Linkedin profile.