Dynamic programming and acceptance theory. Dynamic programming

Hello, Habrakhabr. IN currently I'm working on teaching aid on Olympiad programming, one of the paragraphs of which is devoted to dynamic programming. Below is an excerpt from this paragraph. Trying to explain this topic I tried to illustrate the difficult moments with illustrations as simply as possible. I'm interested in your opinion on how clear it turned out this material. I would also be glad to receive advice on what other tasks should be included in this section.

In many olympiad programming problems, solving using recursion or exhaustive search requires very large number operations. An attempt to solve such problems, for example, by exhaustive search, leads to exceeding the execution time.

However, among exhaustive search and some other problems, we can distinguish a class of problems that have one good property: having solutions to some subproblems (for example, for a smaller number n), you can find a solution to the original problem almost without searching.

Such problems are solved using the method dynamic programming, and by dynamic programming itself we mean the reduction of a task to subtasks.

Sequences

The classic sequence problem is the following.

Fibonacci sequence F n is given by the formulas: F 1 = 1, F 2 = 1,
Fn = F n - 1 + F n- 2 at n> 1. Need to find F n by number n.

One solution that may seem logical and efficient is to solve using recursion:

Int F(int n) ( if (n< 2) return 1; else return F(n - 1) + F(n - 2); }
Using such a function, we will solve the problem “from the end” - we will reduce step by step n until we reach known values.

But as you can see, such a seemingly simple program already at n= 40 works noticeably for a long time. This is due to the fact that the same intermediate data is calculated several times - the number of operations grows at the same speed as the Fibonacci numbers grow - exponentially.

One way out of this situation is to save the already found intermediate results for the purpose of reusing them:

Int F(int n) ( if (A[n] != -1) return A[n]; if (n< 2) return 1; else { A[n] = F(n - 1) + F(n - 2); return A[n]; } }
The given solution is correct and effective. But for this problem a simpler solution is also applicable:

F = 1; F = 1; for (i = 2; i< n; i++) F[i] = F + F;
This solution can be called a “from the beginning” solution - we first fill in the known values, then we find the first unknown value ( F 3), then the next one, etc., until we reach the desired one.

This is exactly the solution that is classic for dynamic programming: we first solved all the subproblems (we found all F i For i < n), then, knowing the solutions to the subproblems, we found the answer ( F n = F n - 1 + F n - 2 , F n- 1 and F n- 2 have already been found).

One-Dimensional Dynamic Programming

To better understand the essence of dynamic programming, we first more formally define the concepts of task and subtask.

Let the initial problem be to find a certain number T with initial data n 1 , n 2 , ..., n k. That is, we can talk about the function T(n 1 , n 2 , ..., n k), the value of which is the answer we need. Then we will consider the tasks as subtasks
T(i 1 , i 2 , ..., i k) at i 1 < n 1 , i 2 < n 2 , ..., i k < n k .

The following one-dimensional dynamic programming problem occurs in various variations.

At n < 32 полный перебор потребует нескольких секунд, а при n= 64 exhaustive search is not feasible in principle. To solve the problem using the dynamic programming method, we reduce original problem to subtasks.

At n = 1, n= 2 the answer is obvious. Let's assume that we have already found K n - 1 , K n- 2 — the number of such sequences of length n- 1 and n - 2.

Let's see what the length of the sequence can be n. If its last character is 0, then the first n- 1 — any correct sequence of length
n- 1 (it doesn’t matter whether it ends with zero or one - 0 comes next). There are only such sequences K n- 1 . If last character is 1, then the penultimate character must be equal to 0 (otherwise there will be two ones in a row), and the first
n- 2 characters - any valid sequence of length n- 2, the number of such sequences is equal K n - 2 .

Thus, K 1 = 2, K 2 = 3, K n = K n - 1 + K n- 2 at n> 2. That is this task actually comes down to finding the Fibonacci numbers.

2D Dynamic Programming

A classic problem in two-dimensional dynamic programming is the problem of routes on a rectangular field.
In different formulations, you need to count the number of routes or find a route that is the best in some sense.

Here are a couple of formulations of such tasks:

Task 2. n*m cells. You can take one-cell steps to the right or down. Count how many ways you can get from the top left cell to the bottom right cell.

Task 3. Given a rectangular field of size n*m cells. You can take one-cell steps to the right, down, or diagonally right and down. Each cell contains a natural number. You need to get from the top left cell to the bottom right cell. The weight of the route is calculated as the sum of numbers from all visited cells. It is necessary to find a route with minimal weight.

A characteristic feature of all such problems is that each individual route cannot pass through the same cell two or more times.

Let's consider task 2 in more detail. To some cell with coordinates ( i,j) can only come from above or from the left, that is, from cells with coordinates ( i - 1, j) And ( i, j - 1):

Thus, for a cell ( i, j) the number of routes A[i][j] will be equal to
A[j] + A[i], that is, the problem is reduced to two subtasks. This implementation uses two parameters − i And j- therefore, in relation to this problem we are talking about two-dimensional dynamic programming.

Now we can go sequentially through the rows (or columns) of array A, finding the number of routes for the current cell using the above formula. First you need to put the number 1 in A.

In problem 3, in a cell with coordinates ( i, j) we can get from cells with coordinates
(i- 1, j), ( i, j- 1) and ( i - 1, j- 1). Let's assume that for each of these three cells we have already found the route of the minimum weight, and placed the weights themselves in W[j], W[i],
W. To find the minimum weight for ( i, j), you need to select the minimum of the weights W[j], W[i], W and add to it the number written in the current cell:

W[i][j] = min(W[j], W[i], W) + A[i][j];

This task is complicated by the fact that it is necessary to find not only the minimum weight, but also the route itself. Therefore, in another array we will additionally record for each cell from which side we need to enter it.

The following figure shows an example of the initial data and one of the steps of the algorithm.

Exactly one arrow leads to each of the already passed cells. This arrow shows from which side you need to come to this cell in order to get the minimum weight recorded in the cell.

After passing the entire array, you will need to trace the route itself from the last cell, following the arrows in the opposite direction.

Subsequence problems

Consider the increasing subsequence problem.

Task 4. Given a sequence of integers. It is necessary to find its longest strictly increasing subsequence.

Let's start solving the problem from the beginning - we will look for the answer, starting from the first terms of this sequence. For each number i we will look for the largest increasing subsequence ending with an element in position i. Let the original sequence be stored in array A. In array L we will record the lengths of the maximum subsequences ending with the current element. Let us find all L[i] for 1<= i <= k- 1. Now you can find L[k] as follows. We look through all elements of A[i] for 1<= i < k- 1. If
A[i]< A[k], то k The th element can become a continuation of the subsequence ending with the element A[i]. The length of the resulting subsequence will be 1 greater than L[i]. To find L[k], you need to go through all i from 1 to k - 1:
L[k] = max(L[i]) + 1, where the maximum is taken over all i such that A[i]< A[k] и
1 <= i < k.

Here, the maximum of the empty set will be considered equal to 0. In this case, the current element will become the only one in the selected sequence, and will not be a continuation of one of the previous ones. After filling the array L, the length of the largest increasing subsequence will be equal to the maximum element of L.

To restore the subsequence itself, you can also store the number of the previous selected element for each element, for example, in an array N.

Let's consider the solution to this problem using the example of the sequence 2, 8, 5, 9, 12, 6. Since there is no element before 2, the maximal subsequence contains only one element - L = 1, and there is none before it - N = 0. Further,
2 < 8, поэтому 8 может стать продолжением последовательности с предыдущим элементом. Тогда L = 2, N = 1.

The only element smaller than A = 5 is A = 2, so 5 can become a continuation of only one subsequence - the one that contains 2. Then
L = L + 1 = 2, N = 1, since 2 is in position number 1. Similarly, we perform three more steps of the algorithm and get the final result.

Now we select the maximum element in the array L and from the array N we reconstruct the subsequence itself 2, 5, 9, 12.

Another classic dynamic programming problem is the palindrome problem.

Task 5. Given a string of capital letters of the Latin alphabet. You need to find the length of the largest palindrome that can be obtained by crossing out some letters from a given string.

Let us denote this string by S and its symbols by S[i], 1<= i <= n. We will consider possible substrings of this string with i th j th symbol, we denote them by S(i, j). We will write the lengths of the maximum palindromes for substrings in a square array L: L[i][j] is the length of the maximum palindrome that can be obtained from the substring S(i, j).

Let's start solving the problem with the simplest substrings. For a single character string (that is, a substring of the form S(i, i)) the answer is obvious - there is no need to cross out anything, such a string will be a palindrome. For a two character string S(i, i+ 1) two options are possible: if the characters are equal, then we have a palindrome, there is no need to cross out anything. If the characters are not equal, then cross out any.

Let us now be given a substring S(i, j). If the first (S[i]) and last (S[j]) characters of the substring do not match, then one of them must be deleted. Then we are left with the substring S(i, j- 1) or S(i + 1, j) - that is, we reduce the problem to a subtask: L[i][j] = max(L[i], L[j]). If the first and last characters are equal, then we can leave both, but we need to know the solution to the problem S(i + 1, j - 1):
L[i][j] = L + 2.

Let's look at the solution using the string ABACCBA as an example. First of all, we fill the diagonal of the array with units, they will correspond to the substrings S(i, i) from one character. Then we start looking at substrings of length two. In all substrings except S(4, 5), the symbols are different, so we write 1 in the corresponding cells, and 2 in L.

It turns out that we will fill the array diagonally, starting with the main diagonal leading from the upper left corner to the lower right. For substrings of length 3, the following values are obtained: in an ABA substring, the first and last letters are equal, so
L = L + 2. In the remaining substrings, the first and last letters are different.

BAC: L = max(L, L) = 1.
ACC: L = max(L, L) = 2.
CCB: L = max(L, L) = 2.
CBA: L = max(L, L) = 1.

If in the task it is necessary to output not the length, but the palindrome itself, then in addition to the array of lengths, we must construct an array of transitions - for each cell, remember which of the cases was implemented (for clarity, in the figure, instead of the numeric values encoding transitions, the corresponding arrows are drawn) .

Let's say there is a problem that we have already solved by dynamic programming, for example, the eternal Fibonacci numbers.
Let's reformulate it a little. Let us have a vector from which we want to obtain a vector. Let's expand on the formulas a little: . You can see that from a vector you can get a vector by multiplying by some matrix, because only the added variables from the first vector appear in the final vector. This matrix is easy to derive, here it is: . Let's call it the transition matrix.

This means that if we take the vector and multiply it by the transition matrix n - 1 times, we get a vector containing fib[n] - the answer to the problem.

Now, why is all this necessary? Matrix multiplication has the property of associativity, that is, (but at the same time it does not have commutativity, which in my opinion is surprising). This property gives us the right to do this: .

This is good because now you can use the fast exponentiation method, which works in . In total, we were able to calculate the Nth Fibonacci number as the logarithm of arithmetic operations.

And now a more serious example:

Example #3: Ramp Sequence

Let us denote a sawtooth sequence of length N as a sequence in which the following condition is satisfied for each non-extreme element: it is either less than both of its neighbors or greater. You need to count the number of sawtooth sequences of digits of length N . It looks something like this:

Solution

First, a solution without a transition matrix:

1) Dynamics state: dp[n] - the number of sawtooth sequences of length n ending with the number last. Moreover, if less == 0, then the last digit is less than the penultimate one, and if less == 1, then it is more.
2) Initial values:
for last in range(10): dp = 9 - last dp = last 3) Recalculation of dynamics:
for prev in range(10): if prev > last: dp[n] += dp if prev< last: dp[n] += dp 4) Порядок пересчёта: мы всегда обращаемся к предыдущей длине, так что просто пара вложенных for "ов.
5) The answer is the sum dp[N] .

Now we need to come up with an initial vector and a transition matrix to it. The vector seems to come up quickly: all states denoting the length of the sequence N . Well, the transition matrix is derived by looking at the conversion formulas.

Transition vector and matrix

Dynamics by subsegments

This is a class of dynamics in which the state is the boundaries of a subsegment of some array. The point is to calculate answers for subproblems based on all possible subsegments of our array. Usually they are sorted in order of increasing length, and the recalculation is based, accordingly, on shorter segments.

Example #4: Packing a string

Here is the Expanded Condition. I'll summarize it briefly:

Let's define a compressed string:
1) A string consisting only of letters is a compressed string. She unclenches into herself.
2) A string that is the concatenation of two compressed strings A and B. It is decompressed into a concatenation of decompressed strings A and B.
3) String D(X) , where D is an integer greater than 1 and X is a compressed string. It is decompressed into a concatenation of D strings decompressed from X .
Example: “3(2(A)2(B))C” expands to “AABBAABBAABBC” .

It is necessary to find out from the string s the length of the shortest compressed string that decompresses into it.

Solution

This problem is solved, as you probably already guessed, by dynamics in subsegments.

1) Dynamics state: d[l][r] - compressed string of minimum length, decompressed into string s
2) Initial states: all substrings of length one can be compressed only into themselves.
3) Recalculation of dynamics:
The best answer has some kind of final compression operation: either it's just a string of capital letters, or it's a concatenation of two strings, or the compression itself. So let's go through all the options and choose the best one.

Dp_len = r - l dp[l][r] = dp_len # The first compression option is just a string. for i in range(l + 1, r): dp[l][r] = min(dp[l][r], dp[l][i] + dp[i][r]) # Try dividing by two compressed substrings for cnt in range(2, dp_len): if (dp_len % cnt == 0): # If it is not divisible, then there is no point in trying to divide good = True for j in range(1, (dp_len / cnt) + 1 ): # Check that all cnt substrings are the same good &= s == s if good: # Try to divide into cnt identical substrings and compress dp[l][r] = min(dp[l][r], len (str(cnt)) + 1 + dp[l] + 1) 4) Recalculation order: direct ascending substring length or lazy dynamics.
5) The answer lies in d.

Example #5:

Dynamics by subtrees

The state parameter of the dynamics along subtrees is usually a vertex, which denotes the subtree in which this vertex is the root. To obtain the value of the current state, you usually need to know the results of all your children. Most often they implement it lazily - they simply write a depth-first search from the root of the tree.

Example #6: Logical tree

Given a hanging tree, the leaves of which contain single-bit numbers - 0 or 1. All internal vertices also contain numbers, but according to the following rule: for each vertex one of the logical operations is selected: “AND” or “OR”. If it is "AND", then the value of the vertex is a logical "AND" from the values of all its children. If “OR”, then the value of the vertex is a logical “OR” from the values of all its children.

It is required to find the minimum number of changes in logical operations in internal vertices such that the value at the root changes or to report that this is impossible.

Solution

1) Dynamics state: d[v][x] - the number of operations required to obtain the value x at vertex v. If this is not possible, then the state value is +inf .
2) Initial values: for leaves, it is obvious that your value can be obtained in zero changes, but it is impossible to change the value, that is, it is possible, but only in +inf operations.
3) Conversion formula:
If this vertex already has a value x , then zero. If not, then there are two options: change the operation at the current vertex or not. For both, you need to find the best option and choose the best one.

If the operation is “AND” and you need to get “0”, then the answer is the minimum of the values d[i] , where i is the son of v .
If the operation is “AND” and you want to get “1”, then the answer is the sum of all values d[i] , where i is the son of v .
If the operation is “OR” and you want to get “0”, then the answer is the sum of all values d[i] , where i is the son of v .
If the operation is “OR” and you need to get “1”, then the answer is the minimum of the values d[i] , where i is the son of v .

4) Recalculation order: the easiest way to implement it is lazily - in the form of a depth-first search from the root.
5) The answer is d xor 1].

Dynamics by subsets

In subset dynamics, the state usually includes a mask of a given set. They are most often sorted in order of increasing the number of units in this mask and recalculated, accordingly, from states that are smaller in inclusion. Lazy dynamics are usually used so as not to specifically think about the traversal order, which is sometimes not entirely trivial.

Example #7: Hamiltonian cycle of minimum weight, or the traveling salesman problem

Given a weighted (edge weights are non-negative) graph G of size N . Find a Hamiltonian cycle (a cycle passing through all vertices without self-intersections) of minimum weight.

Solution

Since we are looking for a cycle passing through all vertices, we can choose any vertex as the “initial” vertex. Let this be vertex number 0.

1) State of dynamics: dp[v] - the path of minimum weight from vertex 0 to vertex v, passing through all vertices lying in mask and only through them.
2) Initial values: dp = 0, all other states are initially +inf.
3) Conversion formula: If the i-th bit in mask is 1 and there is an edge from i to v, then:
dp[v] = min(dp[v], dp[i] + w[i][v]) Where w[i][v] is the weight of the edge from i to v .
4) Recalculation order: the simplest and most convenient way is to write lazy dynamics, but you can get creative and write a search of masks in order of increasing the number of unit bits in it.
5) The answer lies in d[(1<< N) - 1] .

Dynamics by profile

Classical problems solved by profile dynamics are problems of tiling a field with some figures. Moreover, different things can be asked, for example, the number of tiling methods or tiling with a minimum number of figures.

These problems can be solved by exhaustive search in , where a is the number of tiling options for one cell. Dynamics by profile optimizes time along one of the dimensions to linear, leaving only a coefficient in the exponential. You will get something like this: .

A profile is k (often one) columns, which are the boundary between the part that has already been paved and the part that has not yet been paved. This border is only partially filled. Very often it is part of the dynamic state.

Almost always the state is a profile and where that profile is. And the transition increases this location by one. You can find out whether it is possible to switch from one profile to another in a time linear to the profile size. This can be checked every time during the recalculation, but it can also be pre-calculated. We will pre-calculate a two-dimensional array can - is it possible to move from one mask to another by placing several figures, increasing the position of the profile by one. If you pre-calculate, it will take less time to complete and more memory.

Example #8: Domino tiling

Find the number of ways to tile an N x M table using 1 x 2 and 2 x 1 dominoes.

Solution

Here the profile is one column. It is convenient to store it in the form of a binary mask: 0 - an untiled cell of the column, 1 - a tiled cell. That is, total profiles.

0) Pre-calculation (optional): go through all pairs of profiles and check that it is possible to go from one to another. In this problem this is checked like this:

If in the first profile there is a 1 in the next place, then in the second there must be a 0, since we will not be able to cover this cell with any figure.

If in the first profile there is a 0 in the next place, then there are two options - either in the second it is 0 or 1.
If 0, this means that we must place a vertical domino, which means the next cell can be considered as 1. If 1, then we place a vertical domino and move to the next cell.

Examples of transitions (from the top profile you can go to the bottom ones and only there):

After that, save everything in the can array - 1 if you can go, 0 if you can’t.
1) Dynamics state: dp - the number of complete tilings of the first pos - 1 columns with the mask profile.
2) Initial state: dp = 1 - left border of the field - straight wall.
3) Conversion formula:
dp += dp * can
4) The order of traversal is in order of increasing pos.
5) The answer lies in dp.

The resulting asymptotics is .

Dynamics along a broken profile

This is a very strong optimization of profile dynamics. Here the profile is not only a mask, but also a break point. It looks like this:

Now, after adding a break to the profile, you can move on to the next state, adding just one figure covering the left cell of the break. That is, by increasing the number of states by N times (we must remember where the break point is), we reduced the number of transitions from one state to another from to . Asymptotics improved from to .

Transitions in dynamics along a broken profile using the example of a problem about tiling with dominoes (example No. 8):

Reply recovery

Sometimes it happens that simply knowing some characteristic of the best answer is not enough. For example, in the “String Packing” task (example No. 4), we end up getting only the length of the shortest compressed string, but, most likely, we need not its length, but the string itself. In this case, you need to restore the answer.

Each problem has its own way of recovering the answer, but the most common are:

Store the complete answer to the subtask next to the dynamics state value. If the answer is something large, it may require too much memory, so if another method can be used, it is usually done.
Reconstruct the answer, knowing the ancestor(s) of the given state. It is often possible to reconstruct a response by knowing only how it was received. In the same “String Packing”, to restore the response, you can store only the type of the last action and the states from which it was received.
There is a way that does not use additional memory at all - after recalculating the dynamics, go from the end along the best path and compose the answer along the way.

Small optimizations

Memory

Often in dynamics one can encounter a problem in which a state requires a not very large number of other states to be counted. For example, when calculating Fibonacci numbers, we use only the last two, and never turn to the previous ones. This means that you can forget about them, that is, not store them in memory. Sometimes this improves the asymptotic estimate from memory. This technique can be used in examples No. 1, No. 2, No. 3 (in the solution without a transition matrix), No. 7 and No. 8. True, this cannot be used in any way if the traversal order is lazy dynamics.

Time

Sometimes it happens that you can improve the asymptotic time by using some kind of data structure. For example, in Dijkstra's algorithm, you can use a priority queue to change the asymptotic time.

State replacement

In solutions by dynamics, a state necessarily appears - parameters that uniquely define the subtask, but this state is not necessarily the only one. Sometimes you can come up with other parameters and get a benefit from this in the form of a reduction in asymptotic time or memory.

Example #9: Number expansion

You need to find the number of decompositions of the number N into different terms. For example, if N = 7, then there are 5 such expansions:

3 + 4
2 + 5
1 + 7
1 + 2 + 4

Hello, Habrakhabr. I'm currently working on a textbook on Olympiad programming, one of the paragraphs of which is devoted to dynamic programming. Below is an excerpt from this paragraph. Trying to explain this topic as simply as possible, I tried to accompany complex moments with illustrations. I'm interested in your opinion on how clear this material is. I would also be glad to receive advice on what other tasks should be included in this section.

In many Olympiad programming problems, solving using recursion or exhaustive search requires performing a very large number of operations. An attempt to solve such problems, for example, by exhaustive search, leads to exceeding the execution time.

Such problems are solved using the dynamic programming method, and by dynamic programming itself we mean reducing the problem to subtasks.

Sequences

The classic sequence problem is the following.

Fibonacci sequence F n is given by the formulas: F 1 = 1, F 2 = 1,
Fn = F n - 1 + F n- 2 at n> 1. Need to find F n by number n.

One solution that may seem logical and efficient is to solve using recursion:

Int F(int n) ( if (n< 2) return 1; else return F(n - 1) + F(n - 2); }
Using such a function, we will solve the problem “from the end” - we will reduce step by step n until we reach known values.

But as you can see, such a seemingly simple program is already n= 40 works noticeably for a long time. This is due to the fact that the same intermediate data is calculated several times - the number of operations grows at the same speed as the Fibonacci numbers grow - exponentially.

One way out of this situation is to save the already found intermediate results for the purpose of reusing them:

One-Dimensional Dynamic Programming

To better understand the essence of dynamic programming, we first more formally define the concepts of task and subtask.

The following one-dimensional dynamic programming problem occurs in various variations.

At n = 1, n= 2 the answer is obvious. Let's assume that we have already found K n - 1 , K n- 2 — the number of such sequences of length n- 1 and n - 2.

Let's see what the length of the sequence can be n. If its last character is 0, then the first n- 1 — any correct sequence of length
n- 1 (it doesn’t matter whether it ends with zero or one - 0 comes next). There are only such sequences K n- 1 . If the last character is equal to 1, then the penultimate character must be equal to 0 (otherwise there will be two ones in a row), and the first
n- 2 characters - any valid sequence of length n- 2, the number of such sequences is equal K n - 2 .

Thus, K 1 = 2, K 2 = 3, K n = K n - 1 + K n- 2 at n> 2. That is, this task actually comes down to finding the Fibonacci numbers.

2D Dynamic Programming

Here are a couple of formulations of such tasks:

Task 2. n*m cells. You can take one-cell steps to the right or down. Count how many ways you can get from the top left cell to the bottom right cell.

A characteristic feature of all such problems is that each individual route cannot pass through the same cell two or more times.

Let's consider task 2 in more detail. To some cell with coordinates ( i,j) can only come from above or from the left, that is, from cells with coordinates ( i - 1, j) And ( i, j - 1):

Now we can go sequentially through the rows (or columns) of array A, finding the number of routes for the current cell using the above formula. First you need to put the number 1 in A.

W[i][j] = min(W[j], W[i], W) + A[i][j];

The following figure shows an example of the initial data and one of the steps of the algorithm.

Exactly one arrow leads to each of the already passed cells. This arrow shows from which side you need to come to this cell in order to get the minimum weight recorded in the cell.

After passing the entire array, you will need to trace the route itself from the last cell, following the arrows in the opposite direction.

Subsequence problems

Consider the increasing subsequence problem.

Task 4. Given a sequence of integers. It is necessary to find its longest strictly increasing subsequence.

To restore the subsequence itself, you can also store the number of the previous selected element for each element, for example, in an array N.

Now we select the maximum element in the array L and from the array N we reconstruct the subsequence itself 2, 5, 9, 12.

Another classic dynamic programming problem is the palindrome problem.

Task 5. Given a string of capital letters of the Latin alphabet. You need to find the length of the largest palindrome that can be obtained by crossing out some letters from a given string.

BAC: L = max(L, L) = 1.
ACC: L = max(L, L) = 2.
CCB: L = max(L, L) = 2.
CBA: L = max(L, L) = 1.

The Dynamic Programming section is represented by the following calculators:

Investment Allocation Problem. For the reconstruction and modernization of production at four enterprises, funds were allocated C = 80 den. units For each enterprise, the possible increase f i (x) (i = 1, 4) in output is known, depending on the allocated amount.

In dynamic programming problems, the economic process depends on time (or on several periods of time), so a number of optimal solutions are found (sequentially for each stage) that ensure optimal development of the entire process as a whole. Dynamic programming is a mathematical apparatus that allows for optimal planning of controlled processes and time-dependent processes. Carrying out optimization step by step is called a multi-step decision-making process. An economic process is called controlled if it is possible to influence the course of its development.

The dynamic programming (DP) method is based on the principle of sequential optimization: the solution to the original high-dimensional optimization problem is replaced by the solution to a sequence of small-dimensional optimization problems. The main condition for the applicability of the DP method is the possibility of dividing the decision-making process into a number of similar steps or stages, each of which is planned separately, but taking into account the results obtained at other steps. For example, the activity of an industry over a number of business years, or a sequence of tests used in the control of equipment, etc. Some processes (operations) are divided into steps naturally, but there are operations that have to be divided into stages artificially, for example, the guidance process missiles on target.
This principle ensures that the control chosen at any step is not locally the best, but the best from the point of view of the process as a whole, since this control is chosen taking into account the consequences in the upcoming steps.

Let's consider general description of the dynamic programming problem.
Let the multi-step decision-making process be broken down into n steps. Let us denote by ε 0 the initial state of the system, by ε 1, ε 2, … ε n– state of the system after the first, second, n-th step. In general, the state ε k– vector (ε k 1 , …, ε k s).
Management in a multi-step process, a set of solutions (control variables) is called u k = (u k 1 , ..., u k r) taken at every step k and transferring the system from the state ε k-1 = (ε k- 1 1 , …, ε k -1 s) to state ε k = (ε k 1 , …, ε k s).
In economic processes, management consists of the distribution and redistribution of funds at each stage. For example, the production of products by any enterprise is a controlled process, since it is determined by changes in the composition of equipment, the volume of supplies of raw materials, the amount of financing, etc. A set of decisions made at the beginning of the year, the planning period, to provide the enterprise with raw materials, replacement of equipment, and the amount of financing etc. is management. It would seem that in order to obtain the maximum volume of output, the easiest way is to invest the maximum possible amount of funds and use the equipment at full capacity. But this would lead to rapid wear of equipment and, as a consequence, to a decrease in production output. Therefore, product release must be planned in such a way as to avoid undesirable effects. It is necessary to take measures to ensure that equipment is replenished as it wears out, i.e. over periods of time. The latter, although it leads to a decrease in the initial volume of output, provides the possibility of expanding production in the future. Thus, the economic process of production can be considered to consist of several stages (steps), each of which influences its development.
The beginning of a stage (step) of a controlled process is considered to be the moment when a decision is made (on the amount of capital investments, on the replacement of equipment of a certain type, etc.). A stage is usually understood as a business year.
Usually on control at every step u k some restrictions apply. Controls that satisfy these restrictions are called acceptable.
Assuming that the performance indicator k the th step of the process depends on the initial state at this step k-1 and from control at this step u k, we obtain the objective function of the entire multi-step process in the form:
.

Let us now formulate the dynamic programming problem: “Determine the set of admissible controls ( u 1 , …, u n), transferring the system from the initial state ε 0 to the final state ε n and maximizing or minimizing the efficiency indicator F».
Control that achieves the maximum (minimum) of the function F called optimal control u * = (u 1* ,…, u n *).
If control variables u k take discrete values, then the DP model is called discrete. If the variables u k change continuously, then the DP model is called continuous.
Depending on the number of state parameters s and number of control variables r differentiate one-dimensional And multidimensional DP tasks.
The number of steps in a task can be final or endless.

Applied problems of dynamic programming

problem of planning the construction of facilities.

To select the optimal solution when performing programming tasks, it is sometimes necessary to sort through a large number of data combinations, which loads the memory of a personal computer. Such methods include, for example, the “divide and conquer” programming method. In this case, the algorithm provides for dividing the task into separate small subtasks. This method is used only in cases where small subtasks are independent of each other. In order to avoid performing unnecessary work if subtasks are interdependent, the dynamic programming method proposed by the American R. Bellman in the 50s is used.

The essence of the method

Dynamic programming involves determining the optimal solution to an n-dimensional problem by dividing it into n separate steps. Each of them is a subtask with respect to one variable.

The main advantage of this approach is that developers deal with one-dimensional optimization problems of subtasks instead of an n-dimensional problem, and the solution to the main problem is assembled “from the bottom up.”

It is advisable to use dynamic programming in cases where subtasks are interrelated, i.e. have common modules. The algorithm provides for solving each of the subtasks once, and the answers are stored in a special table. This makes it possible not to re-calculate the answer when encountering a similar subtask.

Dynamic programming optimization problem. The author of this method, R. Bellman, formulated the principle of optimality: whatever the initial state at each of the steps and the solution determined at this step, all subsequent ones are chosen optimal in relation to the state that the system takes at the end of the step.

The method will improve the execution of problems solved using enumeration of options or recursions.

Construction of the problem algorithm

Dynamic programming involves constructing a problem algorithm in which the problem is divided into two or more subtasks so that its solution consists of the optimal solution of all subtasks included in it. Next, there is a need to write a recurrence relation and calculate the optimal parameter value for the problem as a whole.

Sometimes at the 3rd step you need to additionally remember some auxiliary information about the progress of each subtask. This is called reversing.

Application of the method

Dynamic programming is used when two characteristic features are present:

optimality for subtasks;
the presence of overlapping subtasks in a task.

When solving using dynamic programming, you first need to describe the structure of the solution. A problem is optimal if the solution to the problem consists of optimal solutions to its subproblems. In this case, it is advisable to use dynamic programming.

The second property of the problem, which is essential for this method, is the small number of subtasks. A recursive solution to a problem uses the same overlapping subproblems, the number of which depends on the size of the input information. The answer is stored in a special table; the program saves time by using this data.

The use of dynamic programming is especially effective when decisions on the essence of the problem need to be made step by step. For example, consider a simple example of the problem of replacing and repairing equipment. Let’s say that a tire foundry’s casting machine produces tires in two different shapes at the same time. If one of the molds fails, the machine has to be disassembled. It is clear that sometimes it is more profitable to replace the second mold in order not to disassemble the machine in case this mold also turns out to be inoperative at the next stage. Moreover, it can be easier to replace both working forms before they begin to fail. The dynamic programming method determines the best strategy for replacing such molds, taking into account all factors: the benefits of continuing to operate the molds, losses from machine downtime, the cost of rejected tires, and more.