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

The Day Our DNS Hit an Undocumented Limit in AWS

🛸 Stealth Infinity 🛸   @StealthInfinity

from Will Bermender on Twitter January 24, 2017 at 07:15AM

Our Finished Cross-Functional Project for Lambda School

Go: A beginners guide to Record UDF’s in Aerospike

Stop Searching For Forex Rates Throughout The Internet. We have an API for that!

Django Setup

Gulf of Evaluation: How Agile has become a Go-to methodology for Software projects?

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

Comparing Insertion Sorting and Merge Sorting Algorithms

Array Algorithm: Rotate an image

The Two Sum Problem: Using a Hash Table (sort of)

Leetcode#382. Linked List Random Node