Dynamic programming: characteristics, methods and examples
By Indeed Editorial Team
Published 18 July 2022
The Indeed Editorial Team comprises a diverse and talented team of writers, researchers and subject matter experts equipped with Indeed's data and insights to deliver useful tips to help guide your career journey.
Dynamic programming is a popular mathematical optimisation and computer programming technique that professionals use to reduce the complexity of processes with several subproblems. Professionals use this in programming, data analytics and software development to optimise coding processes for computer applications. Knowing what this technique is and how to use it in your projects can help you advance your coding and programming skills. In this article, we explore what dynamic programming means, discuss its characteristics, look at some of the methods for computing recursive coding issues and share some examples.
Dynamic programming definition
Professionals use dynamic programming (DP) to solve mathematical optimisation issues. To develop software, DP uses an algorithm that divides complicated coding issues into more manageable subproblems. Coders then derive optimised solutions from these subproblems in the code that, depending on the kind of solution, they then apply to the overarching problem. To save having to recompute input data at a later stage, DP also optimises plain recursion.
There are two important components of DP which include:
Overlap of subproblems
A subproblem is a divided part of a larger, original problem. To illustrate this, consider the Fibonacci sequence, where every number in the sequence is the sum of the two numbers that come before it. To work out the nth value, it's possible to divide the problem into individual subproblems. You can then solve the same subproblem repeatedly and cause them to cross over each other as you uncover solutions. This overlap of subproblems happens with all problems, enabling you to use this kind of programming to divide challenging coding tasks into more manageable items.
Optimal property of substructure
Once you construct solutions from each subproblem and arrive at a satisfactory solution, the optimal substructure property emerges. To function and optimise recursion, the resulting solution from each overlap applies to the overarching problem. Using the Fibonacci sequence as an example, you can use the solution within each subproblem and apply it to the next one to discover the value that comes next in the sequence. This causes the overarching problem to convey optimal substructure property.
Methods of DP
Here are two methods you can use when implementing this form of programming within tasks:
This method involves solving the overarching problem before dividing it into several subproblems. By working out the solution to subproblems in a recursive fashion and taking each result, it's possible to find the solution to overarching problems. Memorisation is a process that can help you avoid calculating the same answer multiple times if you call it more than once. By using this method, professionals can return the results they saved earlier while they continue working on the overall problem.
This method works in the reverse. The bottom-up, or tabulation method, doesn't require you to apply recursion but instead enables you to work out related subproblems first. This kind of tabulation relies on several solvencies. DP uses n-dimensional tables, with n representing values of zero or more. You can use the results of each subproblem solution in the table to compute the original problem.
How to use DP
Here are six steps you can follow to use DP:
1. Identify whether DP is appropriate for the problem
One of the most challenging parts of DP is figuring out whether you can solve a problem using this technique. If you can express your problem solution as a function of solutions to related, broken-down problems, you can use DP and reuse results to save computation time. This technique can solve problems that follow specific counting conditions or probability problems. For example, it can easily solve the following:
the Levenshtein distance problem
longest common subsequence problem
longest increasing subsequence problem
shortest common supersequence
the Rod Cutting problem
0/1 knapsack problem
the matrix chain multiplication
2. Identify the variables of the problem
Once you know that the subproblems have a recursive structure, convey the problem in terms of the parameters of its functions. This can show you which parameters are problematic. A good way to discover the number of changing parameters is to list each subproblem and compare them, as the number of changing parameters is the number of subproblems for you to solve. As an example, determining the nth Fibonacci number involves a single changing parameter, whereas computing edit distance between strings involves two changing parameters. The static parameters and changing parameters represent the subproblems.
3. Convey the recurrence relation
To discover this, it's important to consider how the subproblems relate to each other. Computing the subproblems and expressing the recurrence relation mathematically enables you to compute the primary problem. For example, in the Fibonacci sequence, the subsequent value is always the sum of the two preceding values.
4. Find the base cases
These are subproblems that don't rely on other subproblems. To do this, divide your problem into subproblems. Then, keep dividing until you can't simplify them any further without causing a parameter to become an impossible value based on the restrictions of the problem. Write statements about which values are impossible, then convert these statements about parameters into base cases.
5. Decide how to apply it
You have two options for how to implement the problem: recursively or iteratively. When deciding, work out the base cases and recurrent relations. Also, it's crucial to consider the pros and cons of each implementation method. For example, stack overflow issues typically mean it's unsuitable to have recursion in a production system.
6. Include memorisation
To avoid computing the same subproblems repeatedly and creating delays, it's important to add memorisation, as this stores the results of the function. To do this, be sure to save each solution before each return statement in your memory. Then, use this solution prior to starting another computation. Memorisation exponentially increases the speed of both iterative and recursive approaches.
Here's an example of how to apply the process to the Fibonacci sequence to help you understand how to use each method in DP:
Use the Fibonacci sequence, with every number in the sequence equalling the total of the two numbers that come before. For example:
0, 1, 1, 2, 3, 5, 8,...
When calculating the nth Fibonacci number and solving the entire problem, it's essential to understand that the total of the initial two preceding numbers equals that of the following number in the sequence. You can apply an equation to work out the best solution without dividing the problem into multiple subproblems because you understand how to calculate the future values in the sequence. When n > 1, you can use the appropriate equation to compute the best solution using the top-down method when calculating the nth value of 13:
Fib(n) = Fib(n - 1) + Fib(n - 2) =
Fib(13) = Fib(13 - 1) + Fib(13 - 2) =
Fib(n) = Fib(12) + Fib(11) = 23
After storing the solution in the database, you can then use memorisation and the top-down approach to call on your code strings for more tasks.
For this illustration, use the Fibonacci sequence to divide the whole computations when calculating the nth value in a series. Using the same line of numbers 0, 1, 1, 2, 3, 5, 8, it becomes clear that because 5 and 8 give a sum of 13, you can see that the proceeding value in the sequence results in 13.
When trying to divide a larger problem Fib(n) using the bottom-up method, use the sequence formula Fib(n - 1) + Fib(n - 2), when n > 1 for each smaller problem you're calculating an optimal solution for. For example, if you're computing the subsequent nth values when n = 23:
Fib(n) = Fib(n - 1) + Fib(n - 2) =
Fib(23) = Fib(23 - 1) + Fib(23 - 2) =
Fib(23) = Fib(22) + Fib(21) = Fib(43)
You can then apply the result Fib(43) to the calculation of the following values in the sequence when n = 43:
Fib(n) = Fib(n - 1) + Fib(n - 2) =
Fib(43) = Fib(43 - 1) + Fib(43 - 2) =
Fib(n) = Fib(42) + Fib(41) = Fib(83)
Then you can apply the results further:
Fib(83) = Fib(83 - 1) + Fib(83 - 2) =
You can keep applying them further:
Fib(83) = Fib(82) + Fib(81) = Fib(163)
To calculate the proceeding values in the Fibonacci sequence, you can carry on using this optimal solution. This enables you to divide the starting problem of Fib(n) = Fib(n - 1) + Fib(n - 2), when n > 1.
Explore more articles
- 8 inclusion strategies in the workplace (plus benefits)
- Differences between business intelligence vs analytics
- What is a control chart? (Definition and how to make one)
- An overview guide of tech trends in the upcoming decade
- What is mean, median and mode and how do you calculate them?
- 10 different ways to implement technology in recruiting
- Types of marketing campaign: definition and benefits
- What is marketing automation? (tips, benefits and examples)
- What are virtual ice breakers and how do they work?
- What is encryption and what are some encryption types?
- How to complete customer modelling (with definitions)
- How to find a sample mean: definition and examples