If you have ever encountered problems where you need to determine the best solution based on a certain set of constraints, you probably know that there is a dynamic programming method for this purpose. It is quite a powerful apparatus, and you can use it to solve problems of varying complexity, from finding the largest common subsequence to determining the most favorable combination of items for a backpack. If you want to learn how to apply this method, you need to understand how the dynamic programming apparatus works. All these questions we will consider in this material.
Description of the method
The concept of “dynamic programming” was invented and named in 1940 by Richard Bellman, and changed and supplemented its definition in 1953. Bellman had to spend a lot of time choosing the name, as his boss did not like mathematical terms. So the author of the definition chose the word “programming” instead of “planning” and the word “dynamic” to avoid derogatory and profanity-laced interpretations from his boss. This is how the name “dynamic programming” was formed.
The method of dynamic programming (DP) is one of the main tools for optimization and problem solving in computer science, economics, biology and other fields. In simple words, dynamic programming is a problem-solving method that is based on breaking down a complex problem into many smaller ones.
It is important to consider the following points:
To use this approach effectively, it is necessary to memorize the solutions of subproblems.
Subproblems have a common structure, which allows you to use a homogeneous way of solving them, instead of solving each one separately with different algorithms.
Why it is needed
Optimization problems are effectively solved with the help of DP, for example, if you need to find the largest or smallest value of a function. DP is also actively used in planning problems, where you need to determine the optimal sequence of actions.
Basic concepts
Let’s understand in more detail the basic concepts of the method.
One of the main concepts is the optimal substructure. What is it? In the dynamic programming method, we solve a problem by breaking it down into smaller ones. Optimal substructure means that we can get the best solution if we know the optimal solutions to each of the subproblems.
Another important concept is overlapping subtasks. Here we may encounter a situation where different subproblems have common parts. In such a case, we are said to have overlapping subtasks. To avoid solving the same problem many times, we save the results of subtasks in memory and reuse them while solving larger problems. This helps to speed up the solution process considerably.
For example, suppose we have a problem of finding the largest common subsequence of two strings. We can solve it by dynamic programming, breaking it into smaller subproblems – finding a common subsequence for substrings of each string. In this case, we face overlapping subproblems – the common subsequence for some substrings can already be calculated earlier and stored in memory. Thus, we can avoid repeated computations and solve the problem more efficiently.
DP is a problem solving methodology that is not just a formula or an algorithm, it is more about thinking about how to solve a problem.
This approach requires breaking down the problem into smaller, simpler subtasks (with smaller inputs such as a smaller number, a smaller array, or fewer customizable parameters).
Solutions to the smaller subtasks can be used to solve the larger original problem. An example is the computation of Fibonacci numbers.
It is important to make efficient use of the solutions of the subproblems, for example, by memorizing them, and to use a homogeneous solution method for all subproblems if they share a common structure.
Algorithm of the dynamic programming method
The algorithm of the dynamic programming method consists of several steps:
- Defining the structure of the optimization problem. It is necessary to determine which parameters of the problem are variables, which are constants, what constraints exist on the variables;
- Formulation of recursive formula. It is necessary to express the solution of the problem through the solutions of smaller subproblems. The recursive formula must be correct and have the property of optimal substructure;
- Creating a table to store the results of subtasks. It is necessary to create a table where each cell will store the optimal solution for the corresponding subproblem;
- Filling the table. It is necessary to fill the table, starting with the smallest subproblems and gradually moving to larger ones. When filling the table, a recursive formula is used;
- Obtaining the solution of the original problem. The solution of the original problem is in the last cell of the table.
The algorithm of the DP method can be applied to a wide range of problems, including the problems of finding the shortest path in a graph, optimal work schedule, finding the maximum flow in the network and others. It has a number of advantages, but it also has disadvantages and requires quite a large amount of memory to store the results of subtasks.