Solving Algorithm Problems With Dynamic Programming

For this blog, I’ll be going over what Dynamic Programming is. Learning this topic was challenging especially since there’s not many resources out there that simplify the complexity of Dynamic Programming. I’ll be using the Fibonacci sequence problem as an example, as well as different ways to solve the problem in JavaScript. I hope that I can at least make this topic a bit more understandable for you all!

Dynamic Programming:

Overlapping Subproblems:

To find f(4), we need to know what f(3) and f(2) are. In order to find f(3), we need to know what f(2) and f(1) are, and to find f(2) we need to know what f(1) and f(0) are.

Recursion:

Using recursion to solve this problem is not the most efficient. Its time complexity is O(2^n) which is slower than quadratic runtime!

Memoization:

Tabulated:

Here are the expected outputs:

It’s always best practice to use different test cases to ensure that the solution is working properly. Please feel free to reach out or leave a comment on this blog if I’m missing anything or if there’s any feedback! For more info on Dynamic Programming make sure to check out the resources section below!

Resources:

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store