© TippaPatt / Shutterstock.com
Dynamic programming (DP) is a demanding area of computer programming, with specific skills and techniques for solving problems. Yes, you’ll get by as a software engineer without it, but dynamic programming does have important real-world applications and you may get questioned on it at a developer interview.
If you’re new to dynamic programming or want to refresh your skills, this short article explains what dynamic programming is, with examples and where you can build your DP skills online.
What is dynamic programming?
In computer programming, dynamic programming (DP) is a problem-solving method that structures and simplifies complicated problems by breaking them down into a cascade of overlapping sub-problems. By applying DP multiple classes of problems can be efficiently solved.
DP originates in mathematics and is applicable in diverse fields from bioinformatics to water resource engineering to economics.
How does Dynamic Programming work in computer science?
Dynamic programming has to be appropriately applied to be used in computer programming. A problem must have two characteristics to be suitable for DP:
- An optimal substructure: A specified problem has optimal substructure property if its optimal solution can be derived from optimal solutions of its subproblems.
- Overlapping subproblems: The problem in question should be able to be broken down into a cascade of reusable subproblems or a recursive algorithm that can repeatedly solve subproblems without generating new ones.
These two properties are key to using DP. If the optimal solution is found using subproblems that are non-overlapping, DP cannot be used. Instead, divide and conquer is used. Similarly sorting algorithms like merge sort and quick sort aren’t DP.
Recursion and dynamic programming
Recursion is a key property of the optimal substructures used in DP. Recursion is simply a process repeating itself, like when you stand between two mirrors and your reflection is repeated over and over again (the Droste effect).
The optimal substructures have cascades of problems that continually solve themselves and the primary problem recursively.
A recursive algorithm in DP doesn’t generate new sub-problems, keeping the amount of space taken up by the individual overlapping subproblems small. Ideally, the same sub-problems should be solved over and over again.
Key types of dynamic programming?
There are two types or methods of DP which depend on how you approach a problem. Both methods use memoization, storing, and tabulating solutions so that they can be retrieved quickly, saving the time of repeating the computation.
Top-down
In the top-down approach, the solution to a problem is recursive, allowing the memoization of solutions to the overlapping subproblems. Subsequent new subproblems are solved by referring to the memoized data cache to see if a solution is already present. If the subproblem has not been solved previously it and its solution are added to the memoization cache.
Top-down DP is straightforward to understand and use as it facilitates targeted solving of subproblems. You can debug it easily but this recursion approach can use up a lot of cache memory, which can lead to stack overflow errors.
Bottom-up
The bottom-up approach, also known as tabulation or table filling, uses tabulation for creating a record of stored subproblems and solutions. It then uses the tabulated solved subproblems for a bottom-up reformulation of the problem. Smaller subproblems are solved, with the solutions leveraged to solve bigger subproblems. The For loop can be used to iterate the subproblems.
Example: Dynamic programming and the Fibonacci series
A practical example of dynamic programming in action working with the Fibonacci series:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55…
With Fibonacci numbers (Fn), any number in the sequence is the sum of the previous two numbers. As the value of ‘n’ in Fn increases, the scale and complexity of the computation of these numbers increase.
DP can be used to calculate any Fibonacci number. By using DP, you don’t have to generate a recursive tree or solve problems over and over again. Simply use previously calculated values. Here is how the code looks for an implementation of this series using the top-down method:
©History-Computer.com
Why is dynamic programming important?
Dynamic programming isn’t a prominent part of the modern programming landscape. This is because it is not usually directly used in contemporary production-level development
Many competent engineers have established themselves without having more than passing knowledge of DP, despite it being part of leading programming languages like:
- Python
- JavaScript
- Ruby
- PHP
- Perl
- Lua
Working knowledge of DP is valuable to engineers because it can help developers create software applications that are better structured and more efficient.
The modern shared service architecture consists of independent applications accessing the resources (memory, processing power, network capacity, costs) of a shared pool. Poorly structured code with poor attention to problem-solving can lead to the unnecessary consumption of resources, impacting the performance of other applications. DP helps to refine software code to prevent this from happening.
Real-world examples of dynamic programming
There are many examples of real-world software applications that use DP to stay nimble and efficient and minimize the system requirements for running them. Here are some examples:
- Google Maps: In Google Maps, DP is used to identify the shortest path between a single start point and a variety of destinations.
- Search engines: To calculate the degree of similarity between two pieces of online content.
- Plagiarism software: Development of document distance algorithm to aid detection of the level similarity between text documents.
- Networking: Transfer of data from a single source to several different receivers sequentially.
- Spell checkers: The edit distance algorithm that is used to quantify how dissimilar two words are and calculate the number of operations required to change one word into another.
Databases/knowledge base cache: storage of common queries/requests in accessible local memory or caches. DP helps prevent the repeated fetching of commonly used data from servers, in favor of local storage.
Example dynamic programming interview questions
If you are looking for your next software engineer or developer job, knowledge of DP will give you the edge in job interviews.
DP is a big thing in tech interviews. Leading tech companies like Google and Amazon routinely challenge candidates with DP questions that have to be worked out on the spot! This is to test how developers think, and if they will break down tasks and find the most resource-efficient ways to solve problems.
Here are some examples of dynamic programming interview questions and answers
Aside from the Fibonacci equation shown above, here are some common dynamic programming interview questions, with example answers and solutions:
Question 1: Can you explain the advantages and disadvantages of Memoization?
(Hint: this is a question about the pros and cons of the top-down approach in DP)
Answer:
The advantages of memoization include:
- The coding is easy
- A problem can be approached by writing a wrapper or annotation that will automatically execute the recursive function
- Answers can be procured from a cache and used for multiple problems
The main disadvantage of memoization is that if you have a large or deep number of computations, you may rapidly run out of stack space.
Question 2: You’re climbing stairs. You can climb either one or two steps at a time. How many different ways are there to climb to the top?
(Hint: this question is known as the ‘climbing stairs’ problem)
Answer: Take a look at the approach to this common coding interview question in this video:
Where can I practice dynamic programming?
Building skills in dynamic programming strengthens the thinking skills and problem-solving of developers. DP can also help you think more holistically about problems and develop unusual but effective solutions. If it is time for you to get training or certifications in DP, here are 3 of the best online courses:
Once you’re up to speed, practice makes perfect!
- This short online course from Topcoder will take you through the basics of DP in 15 minutes: Dynamic Coding: From Novice to Advanced
- Udemy runs a popular DP course covering both the top-down and bottom-up approaches: Dynamic programming
- If you’re on LinkedIn, why not pick up some excellent tuition and a course certification by taking their Fundamentals of Dynamic Programming course?
Rounding up
Dynamic programming may not be part of your developer stack, but it matters to the corporations that you want to work for. Understanding and learning DP will not only land you jobs but also refine your skills and help you write the clean code that your lead developer will love!
