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:

Dynamic Programming is used for solving a complex problem by breaking it down into a collection of simpler subproblems solving each of those subproblems just once, and storing the solutions.

Overlapping Subproblems:

A way to determine whether or not we need to use Dynamic programming for a problem is if it has overlapping subproblems. Overlapping subproblems means solving the same subproblem multiple times in order to find the solution. Here’s an example of an overlapping subproblem:

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:

One way to solve problems using Dynamic Programming is recursively. Here’s the fibonacci solution:

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:

Ensures that a function doesn’t run for the same inputs more than once by keeping a record of the results for the given inputs. Instead of solving a subproblem multiple times, we can solve it once by storing the cached results.

Tabulated:

Another form of Memoization and also known as the Bottom-up approach is where we store the results in an array. You can then iterate over that array to find the result. This leads to better space complexity!

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:

--

--

--

Love podcasts or audiobooks? Learn on the go with our new app.

Recommended from Medium

Data Engineering Weekly #21: Metadata Edition

Over the past 48 hours I have proposed this idea to the CEOs

Super charge build time in multi-module project with gradle’s dependency resolution

CyberSecLabs ‘Unroot’ Walkthrough

How to crack machine coding round?

Web3.0 is here, why should I care about it?

Use Python to call Drupal 9 core RESTful API to create new content

How to use AWS-CLI for launching EC2 instances

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
Bryam Vicente

Bryam Vicente

More from Medium

How to Create a Successful Software Development Team?

Why I quit using inheritance & instead started using object composition.

I’m Learning To Master The Coding Interview

How to make your tests fail when they try to access the network (Python)