1. Preface

For software engineers, they must be familiar with the field of "Algorithms and Data Structures", and the famous formula "algorithm + data structure = program" proposed by Nicklaus Wirth, the father of Turing Award winner Pascal, shows the importance of algorithms.

When climbing the mountain peak in the field of algorithms, we went all the way from sorting, searching, greed and other algorithms, and finally came to the top of the mountain, and when we were about to sigh "at a glance of the mountains", we suddenly found that there was a higher cliff - dynamic programming (commonly known as DP) in front of us.

At the same time, when we brush leetcode and interview with large manufacturers, we often encounter problems and scenarios that need to be solved by using dynamic programming; In addition, in our daily complex business development, we can also see the application scenarios of dynamic programming.

The problem of dynamic programming is very, very classic and skillful, but it is by no means a far-fetched concept.

Today, let's learn the "routine" of dynamic programming, mainly from the following topics:

1. The mysterious dynamic programming mainly leads to the concept of dynamic programming, that is, the academic perspective that everyone usually sees. 2. Entering into dynamic programming, this chapter mainly explains what I understand as dynamic programming, as well as the core ideas refined in the learning process, as well as the derivation process. 3. Practical practice and application of dynamic programming, using an example to deduce the whole process of implementation, how to write a violent recursive version, a memory search version, and the final state transition equation version; Finally, there is an introduction to the application of dynamic programming in after-sales business.

If there is anything wrong with the article, you are welcome to point it out, thank you!

2. Mysterious dynamic programming

2.1 What is dynamic programming

Dynamic programming (DP) is a method used in mathematics, management science, computer science, economics, and bioinformatics to solve complex problems by breaking down the original problem into relatively simple subproblems. Dynamic programming is often applied to problems with overlapping subproblems and optimal substructural properties.

dynamic programming is a method for solving a complex problem by breaking it down into a collection of simpler subproblems.

The above definition is from Wikipedia, and it feels a bit abstract to see the definition. To put it simply, dynamic programming is actually that given a problem, we break it down into sub-problems until the sub-problems can be solved directly. Then, save the sub-question answers to reduce double-counting. Then, according to the answer of the sub-question, it is a method to obtain the solution of the original problem.

In general, these subproblems are similar and can be deduced recursively by functional relations. Then, dynamic programming is committed to solving each sub-problem once and reducing double calculations, such as the Fibonacci sequence, which can be regarded as an entry-level classical dynamic programming problem.

2.2 Application scenarios of dynamic programming

2.2.1 Optimal solution to the problem

This kind of problem will generally ask you to find the largest subarray, the longest ascending subarray, the longest ascending subsequence or the longest common substring, subsequence, and so on. There are also the well-known backpack issues, as well as the most reasonable use of coupons issues.

2.2.2 Seek feasibility

Lets you determine if there's a path that adds up to x (if found, it's true; If you can't find it, it's False), or if you can judge whether you can find a path that meets certain conditions, then this kind of problem can be summarized as a feasibility problem, and can be solved using dynamic programming.

2.2.3 Finding the Total

In addition to finding the maximum value and feasibility, finding the total number of solutions is also a common type of dynamic programming problem. For example, given a data structure and constraints that allow you to calculate all possible paths for a scheme, then this kind of problem is a problem of finding the total number of schemes.

3. Walk into dynamic programming

This chapter mainly explains what I understand as dynamic programming, as well as the core ideas refined in the learning process, and the derivation process.

3.1 The core idea of dynamic programming

The core idea of dynamic programming is that dynamic programming is an algorithmic strategy that decomposes problem instances into smaller, similar sub-problems, and stores the solutions of sub-problems to avoid computational duplication of sub-problems, so as to solve the optimization problem. The essence of dynamic programming is the idea of divide and conquer and solve redundancy.

If you use an easy-to-understand sentence, then it should be: dismantle the numerator problem, remember the past, and reduce double counting. Let's take a simple everyday example:

A: 21+12+3+64+45+6+70+37 , what is the value of this equation? B: Well, it took 3 minutes to figure out that the answer is 258A: What is the value of the equation if you write "+2" to the right of the equation above? B: Quick answer "260" A: How did you know the answer so quickly B: Just add 2 to 258

3.2 Dynamic programming problem-solving routines

Let's introduce the solution of dynamic programming in a few steps, which are:

1) Try to Design a Brute Force Recursion Model: The Point! This is the basis 2) Analyze whether there are duplicate solutions: (list the call process, you can only list the first few layers) 3) Use the memory search method: space for time, reduce repeated calculations4) State transition equation: refine the analysis of DP table structure and recursive model, and realize the state transition equation of dynamic programming

3.2.1 Try a brute-force recursive model

This is the first step to realize the dynamic programming algorithm, and it is also the most basic and important precondition. In this step, we need to try to design a recursive model according to the actual scenario and problem, first we need to transform the problem into a sub-problem of the same kind of problem that has been reduced in scale, and we also need to determine the clear conditions that do not need to continue recursion, which is commonly known as the Base Case, and we can't let recursion enter an endless loop.

The brute-force recursive model has a fatal flaw, that is, it only obtains the results of the sub-problems, but does not record the solution of each sub-process; This leads to double counting, which increases the time complexity of the algorithm. For example, in some problems on Leetcode, if you only use brute force recursion to implement the algorithm, it will report "time limit exceeded" when submitting.

3.2.2 Analyze duplicate solutions

Also called "repeating sub-problems", from the "Fibonacci sequence" to solve the problem, we know that if we recursively go to this problem, we will encounter many "repeating sub-problems".

The Fibonacci sequence states that the first term is 1, the second term is 1, and each subsequent term F(n) = F(n-1) + F(n-2). Let's start the process of solving item 7 as follows:

We only need to expand the value of item 7 on the whiteboard, and we will find that there will be many repetitive processes in the whole recursion process, and then we can use dynamic programming to optimize the solution.

3.2.3 Memory search method

For recurring sub-problems, solve them only the first time they encounter them, and save the answers so that they can be directly referenced when they are encountered again without having to resolve.

One of the most striking features of the problem targeted by dynamic programming is that the subproblems in the sub-problem tree to which it corresponds are repetitive.

For example, in the above Fibonacci sequence, after we solve F(5) once, we save its value, and the next time we need to find F(5), we can take it directly, reducing the process of repeated solving. In the same way, doing this for every solved value is called dynamic programming.

According to the number of variable parameters in the algorithm, the cached DP array of several dimensions is analyzed and defined.

3.2.4 State Transition Equation

We might as well think of the state transition equation as a recursive relation, that is, how to find an unknown expression from the known.

The final equation is completely detached from the original meaning of the original question, and is based on the recursive model of brute force and the known conditions given in the problem, such as:

Base Case是什么？

What is the range of variadic parameters?

How does the ubiquitous location depend?

What is the final position?

Other...

Combined with the above known conditions, an algorithm (that is, the state transition equation) is extracted, which fills and assigns the cached DP array, and finally returns a position in the DP array that is the value we finally solve.

Therefore, the steps and solution process of designing dynamic programming are shown in the following figure:

4. Dynamic planning and application

In this chapter, we will introduce and explain through an example of dynamic programming and a scenario of practical application of dynamic programming in an invoice system.

The process of our actual dynamic programming algorithm will be carried out according to the process introduced in the dynamic programming problem solving routine described above, which are:

4.1 Robot Positioning Problems

The topics are as follows:

Given 1~N positions, there is a robot walking in it, and it can only take one step to the left and right at a time.

The total number of steps taken by the robot must be equal to restSteps, how many ways are there to calculate the steps that meet the conditions?

For example, given 4 positions, the robot sends out from position 2, walks 6 steps, and finally reaches position 4, how many ways are there in total?

Note: If the current robot goes to the leftmost 1 position, it can only go to the 2 position; If you go to the N position, you can only go to the N-1 position.

Step 1: Try to design a brute force recursion model

This topic is a very classic introductory question of dynamic programming, and some students may be a little confused after seeing it, and they don't know how to solve it. In fact, the following analysis can be made:

What is the base case for exiting recursion: when the number of steps remaining (restSteps) is equal to 0, i.e. restSteps == 0

How to define a move that satisfies the condition: when the remaining steps (restSteps) are equal to 0 and the robot is just stopped at the aim position, i.e. restSteps == 0 && cur==aim

Recursive Scenarios:

If the current robot goes to the leftmost position of 1, it can only go to the position of 2,

If you go to the N position, you can only go to the N-1 position

Otherwise, the robot can go left or right

At this point, we can derive the final recursive model as follows:

Based on the above analysis, we can write the code for the brute-force recursive version as follows:

So far, we have designed the code of brute force recursion and completed the first step of the dynamic programming problem solving routine; Let's see if there are duplicate solutions.

Step 2: Analyze whether there are duplicate solutions

We analyze the following data:

int cur = 2; //开始位置

int restSteps = 4; //剩余步数

int aim = 4; //目标位置

int N =4; //位置总数

There are a total of 4 positions, and you need to start from position 2, and the robot will take 4 steps to finally stop at position 4. (Attention!) Here in order to make it easier for us to expand all the moves on paper, we deliberately set the number of steps to 4)

The first way to walk: the robot starts from the No. 2 position, walks to the No. 3 position (3 steps remaining), and then walks to the No. 4 position (2 steps remaining); Go to position 3 again (1 step remaining); Finally reach position 4 (0 steps remaining)

The second way of walking: the robot starts from the No. 2 position, walks to the No. 3 position (3 steps remaining), and then walks to the No. 2 position (2 steps remaining); Go to position 3 again (1 step remaining); Finally reach position 4 (0 steps remaining)

The third way to walk: the robot starts from the No. 2 position, walks to the No. 1 position (3 steps remaining), and then walks to the No. 2 position (2 steps remaining); Go to position 3 again (1 step remaining); Finally reach position 4 (0 steps remaining)

The moving process is detailed in the following figure:

Analyzing the sub-process of the first move and the first step of the second move (2→3), we find that the current position (cur) is from 2 to 3, and there are still 3 steps left in the remaining steps (restSteps), which is a process of repeated counting.

Analyzing the sub-process of the second move and the third step (2→3) of the third move, we can also find that the current position (cur) is from 2 to 3, and the remaining number of steps (restSteps) is still 1 step, which is also a process of double counting.

If the robot can take more steps, the more moves can be counted; The more sub-processes that are generated at the same time, the more double counting.

Therefore, if we expand the previous three moves, we will know that there is indeed a duplicate solution; So, we can optimize it further.

Step 3: Memorization Search

First of all, we need to analyze how many variable arguments there are in the whole recursive call process, according to the above recursive code version, we know that the function process has a total of 4 input arguments, and there are 2 fixed input arguments, which are array length N and target position aim; There are 2 variable input parameters, which are the current position cur where the robot is located, and the remaining number of steps restSteps.

Here we only focus on the variable parameters, so we can see that we need to prepare a 2-dimensional array to cover all the variations of these two parameters, and the range of cur is up to N. i.e.: dp[N+1][restSteps+1], where +1 is for ease of understanding that it can encompass all ranges and calculations.

The first dimension (row) of the dp array represents all the positions that the robot can go, that is, the range is from 1~N. The second bit (column) of the dp array represents the number of steps left by the robot, i.e. in the range from 0~restSteps.

PS: Interested students can print the running time of these two algorithms, with the larger the value of restSteps, the more obvious the advantages of algorithm 2, I will not demonstrate it here.

Step 4: State Transfer Equation

The state transition equation can be understood as a recursive relation, which is how to find an unknown expression from the known.

Then, we need to analyze the recursive relationship of the brute-force recursive version above, and be able to derive as follows:

1) Recursively invoke the model and populate the dp array according to the base case

The condition for stopping the recursive call (base case) is: when the number of remaining steps (restSteps) is equal to 0, and there are two cases:

When the current position of the robot (CUR) just stops at the target position (AIM), it is 1 walk;
Otherwise, there are 0 moves.

Therefore, when the remaining steps (restSteps) are equal to 0, it means the 0th column of the dp array; Then, according to the position where the robot finally stays is equal to the target position, we assign dp[aim][0] to 1, and the first column of the other rows is 0, so that we fill the first column of the dp array.

2) Populate the dp array according to special scenarios

What special scenarios are given in the title, and what information is revealed?

When the robot goes to the leftmost position No. 1, it can only go to the right to the No. 2 position, and the corresponding remaining number of steps is subtracted by 1;
When the robot goes to the rightmost position N, it can only go to the left to the N-1 position, and the corresponding remaining number of steps minus the definition above 1 shows that the first dimension of the dp array represents the position range, therefore:

填充dp数组第一行的逻辑为：dp[1][restSteps] 依赖于 dp[2][restSteps - 1]

填充dp数组最后一行的逻辑为：dp[N][restSteps] 依赖于dp[N-1][restSteps - 1]

3) The prevalent position depends on padding dp arrays

This is the most central part of the state transition equation, because the dependence of universal positions is relatively secretive, and it also accounts for the vast majority of the position space of the dp array.

Again, the way we analyze is to look for clues from the recursive model of brute force.

Because if a robot is not on the far left or on the far right, then the position of its next move can be left or right, and the dependencies are as follows:

dp[cur][restSteps] = dp[cur+1][restSteps -1] + dp[cur - 1][restSteps -1]

That is, it depends on the value in the upper left corner of the previous row plus the value in the lower left corner of the next row.

4) The location of the final return

If we find an unknown expression of the state transition equation from the known conditions and populate the dp array, then we need to know where in the dp we will finally solve.

Again, we need to look at the brute force recursive model.

When calling the process recursive method, the initial input argument is as follows:

int cur = 2; //开始位置

int restSteps = 4; //剩余步数

int aim = 4; //目标位置

int N =4; //位置总数

... return process2(cur,restSteps,aim,N,dp);

The variable arguments are: cur and restSteps are the final values we need to return from the dp array.

So, cur is equal to 2 and restSteps is equal to 4, we need to return dp[2][4].

The derivation process is as follows:

Eventually, based on the derivation process above, the final state transition equation code is as follows:

4.2 Invoice items - the best match of the invoicable amount

This is a functional scenario in our project, in the process of invoicing, the financial staff will need to issue an invoice of the same amount to the consumer, so it is necessary to match the product records with the most similar amount according to the amount consumed by the user, and the specific process is as follows:

1. Get the list of goods that meet the requirements from the product line, and the amount of goods is randomly distributed

2. The financial staff enters the invoice amount

3. The system automatically checks the list of commodities closest to the invoice amount

Our analysis of this problem belongs to the category of dynamic programming algorithms, which is similar to the upgraded version of the backpack problem, which is to record the path of the maximum value final result, so as to deduce the path elements in reverse.

The specific code is as follows:

The implementation process of the dynamic programming algorithm is the same as the above problem solving routine, and it will not be expanded here due to space.

5. Conclusion

Dynamic programming is a challenging topic and field, where the changes are unpredictable, and at the same time, it is also a thunderbolt for us to solve complex problems;

We start from the very beginning of the attempt, step by step to deduce, this is the process of state transition, to write the final dynamic programming code directly in one step is to continue to practice and summarize.

Writing this, I am deeply afraid, if everyone has a harvest, it will be a great good!

Author: Thrive Preferred Technology Community

Source: https://zhuanlan.zhihu.com/p/618731459

Get started with dynamic programming