In my impression, dynamic programming is the most difficult one. In my opinion, dynamic programming is the most difficult.

background

My niece is 5 years old and now she starts to learn addition and subtraction. Every time she does math, she can’t do without her little fingers. If she is more than 5, she starts to count the fingers of the other hand

I asked her one day

“What’s 1+1+1+1+1?”

“Pick up little finger, start to count, five!”

“What about adding another one?”

“Six, of course.” – Blurt it out

“How did you get so fast this time?”

“That was just five. Add one to make six.”

“So you don’t have to recalculate because you remember the answer was 5! Dynamic programming is: you save time by remembering things from the past.”

Get into the business


Play, play, play. Don’t take it d p Kidding! \color{red}{don’t make fun of dp! }

Take a look at the entry for the Popular Science Encyclopedia of China

Dynamic Programming (DP) is a branch of operations research. It is the process of optimizing the decision-making process. In the early 1950s, THE American mathematician R.Bellman and others put forward the famous optimization principle when studying the optimization problem of the multi-stage decision process, thus creating the dynamic programming. Dynamic programming is widely used, including engineering technology, economy, industrial production, military and automation control and other fields, and has achieved significant results in the backpack problem, production and operation problem, capital management problem, resource allocation problem, shortest path problem and complex system reliability problem.

See not over of children’s shoes to skip, the hour we simple point

Actually, this is probably the easiest dynamic programming problem you can do.

What can we see about this problem?

We know that is the last step 1 will be calculated so fast, most thanks to calculate before the answer is 5, if we put the question as a child, I want to calculate the answer to every step, you can list an equation: f (x) = f (x – 1) + 1, everyone don’t to f (x) the mess, I put it as a simple way.

Where, f(x) is the value of which step, set an initial value, x > 0, then the first step

f(1) = 1;

f(2) = 2;

.

f(6) = 6

In the world of a program, what is used to store a data structure that can record the previous result values?

Obvious: arrays. We just use the subscripts to store the bashi, and that’s the dynamic in dynamic programming, which is to define some boundaries and initialize.

Here’s a training problem


Don’t look at it. It’s also an easy one \color{red}{don’t look, this is also a simple problem}

Leecode 322: You have three kinds of coins, 2 yuan, 5 yuan and 7 yuan. There are enough coins for each. You need 27 yuan to buy a book

Why does it feel like we’re back in grade school word problems?

— Simple analysis: Minimal coin combination -> Use as large a coin as possible

Who came up with this stupid problem? It’s so easy

7+7+7=21,21+2+2+2=27, 6 coins

Oh my god

7+5+5+5+5=27, 5 coins

We can think about it in a very violent way, in a small way, it doesn’t add up to more than 27, for example

7+7+7+7 > 27 (Excluded)

7+7+7+5 or 7+7+7+ 2+2+2 6

.

Exhaustive is too slow and involves a lot of double counting, so what if I want the smallest coin combination of any value up to 27? Think about it.

Since the computer can hold the previous contents in memory, and it’s fast, obviously, we can open an array to hold the previous state.

Focus on early warning

1.1. Dynamic programming Component 1: Determining status

To put it simply, when solving dynamic programming, we need to open an array. What does each element of the array f[I] or f[I][j] stand for, similar to what does x, y, and z stand for in math

Solving dynamic programming requires two consciences:

  • The last step
  • subproblems

The last step

As we said in the first problem, the last step is 5. So in this case, even though we don’t know what the optimal strategy is, the optimal strategy must be K coins, A1, a2,…. The ak values add up to 27

So there must be a last coin :ak.

So minus this coin, the face value of the first coin adds up to 27 minus ak

Key point 1:

  • We don’t care how the first k-1 coin spelled 27-ak (there could be one or 100 ways to spell it), and we don’t even know ak and K yet, but we’re sure the first coin spelled 27-ak

Key point 2:

  • Because it’s the optimal strategy, it has to have the least number of coins to spell 27-AK, otherwise it’s not the optimal strategy

subproblems

  • So we asked: what is the minimum number of coins to spell 27-AK
  • The original question was what is the minimum number of coins to spell 27
  • We turned the original problem into a subproblem on a smaller scale: 27-AK
  • To simplify the definition, let’s say that state f of x is equal to the minimum number of coins to spell out x

Wait, we don’t know what ak is in the last quarter

  1. Obviously, the last coin can only be 2,5 or 7
  2. If ak is 2, f of 27 should be f of 27 minus 2 plus 1, where 1 is the last coin 2.
  3. If ak is 5, f of 27 should be f of 27 minus 5 plus 1, where 1 is the last coin 5.
  4. If ak is 7, f of 27 should be f of 27 minus 7 plus 1, where 1 is the last coin 7.

So using the fewest number of COINS = f (27) = min {f (27-2) + 1, f (27-5) + 1, + 1} f (27-7)

1.2. Dynamic Programming Component 2: Transfer equations

Let’s say state f of x is equal to the minimum number of coins to spell out x

For any x: f(x) = min{f(x-2)+1, f(x-5)+1, f(x-7)+1}

1.3. Dynamic Programming Component 2: Initial conditions and boundary cases

Ask questions

  1. What if x minus 2, x minus 5, and x minus 7 are less than 0?
  2. When does it stop?

1.3.1

If you can’t spell Y, define f[Y] = infinity

For example, f[-1], f[-2] = infinity

F [1]=min{f(-1)+1, f(-3)+1, f(-6)+1}

Initial condition: F [0] = 0

2.4. Dynamic programming Component 2: Computation sequence

Calculation: F [1], F [2]… f[27]

When we get to f[x], f[x-2], f[x-5], f[x-7], we’ve got the result

As shown in figure:

F [x] = the minimum number of coins to spell out x

F [x] = infinity means you can’t spell x with a coin

Reference code

public  static  int coinChange(int [] A, int M ) {
 int[] f = new int[M+1];
 int n = A.length;
 f[0] = 0;
 int i,j;
 for (i = 1; i<=M; i++) {
    f[i] = Integer.MAX_VALUE;
    for (j = 0; j< n; j++) {// Boundary condition judgment
        if(i >= A[j] && f[i - A[j]] ! = Integer.MAX_VALUE) { f[i] = Math.min(f[i - A[j]] +1, f[i]);
          // System.out.println(i + "=" +f[i]);}}}if (f[M] == Integer.MAX_VALUE) {
    f[M] = -1 ;
 }
 return  f[M];
}
Copy the code

😄


The core code is 4 Okay, that’s easy \color{red}{core code is only 4 lines, is very simple ~}

Of course, this problem can also be achieved through the method of pruning, here is not much to repeat

Let’s do another training problem

Or another question, a question is too arbitrary ~

Leecode 62: different paths

A robot is located in the upper left corner of an m x N grid (the starting point is marked “Start” in the image below).

The robot can only move one step down or to the right at a time. The robot tries to reach the lower right corner of the grid (marked “Finish” in the image below).

How many different paths are there?

Look at the above problem solving steps, step by step

2.1. Dynamic programming Component 1: Determining status

The last step

No matter how the robot reaches the lower right corner, there is always a final move: – to the right or down

If shown, let’s set the lower right coordinate to be (m-1,n-1).

So the position of the robot before the last step is m minus 2,n minus 1, or m minus 1,n minus 2.

subproblems

So, if the robot has x ways to go from the top left corner to (m-2,n-1), and Y ways to go from the top left corner to (m-1,n-2), then the robot has x +Y ways to go to (m-1,n-1).

The question becomes, how many ways can the robot go from the top left corner to (m-2,n-1) or (m-1,m-2)?

If it goes to (m-2,n-1), as shown in the figure:

We can just kill the last column

Similarly, if you go to m minus 1,n minus 2 rows, you subtract one row.

Status:

Let f[I][j] be how many ways the robot can go from the top left corner to (I,j).

2.2. Dynamic programming Component 2: Transfer equations

For any lattice:

f[i][j] = f[i-1][j] + f[i][j-1]

1 2 3

1 represents how many ways the robot can go [I][J]

2 represents how many ways the robot can get to F [i-1][J]

3 is how many ways the robot can go to F [I][j-1]

2.3. Dynamic Programming Component 3: Initial and boundary conditions

Initial condition: F [0][0]=1, because the robot has only one way to get to the upper left corner

Boundary case: I =0 or j=0, then the previous step can only come in one direction, that is, row 0 or column 0. Each step has only one case, then f[I][j] = 1, and other regions satisfy the transition equation.

3.4. Dynamic programming Component 4: Computation order

Row by row. Why row by row?

F [0][1] and F [1][0] have already been calculated. Similarly, these two coordinates have also been calculated by column calculation. There is no need to calculate again.

  • f[0][0] = 1
  • Calculate line 0: f[0][0], F [0][1],… ,f[0][n-1]
  • Calculate line 1: F [1][0], F [1][1],… ,f[1][n-1]
  • .
  • Calculate line m-1: f[m-1][0], F [m-1][1],… ,f[m-1][n-1]

Time complexity: O(mn)

Reference code

public int uniquePaths(int m, int n) {
    int[][] f = new int[m][n];
    int i,j;
    for (i = 0; i<m; i++) {
        for (j = 0; j< n; j++) {
            if (i == 0 || j == 0) {
                f[i][j] = 1;
            } else {
                f[i][j] = f[i -1][j] + f[i][j-1]; }}}return f[m-1][n-1];
}
Copy the code

To summarize

What problems can WE do with dynamic programming?

Counting 1.

  • How many ways to go to the bottom right
  • How many ways can I pick k numbers and the sum of yes is sum

2. Find the maximum and minimum values

  • The maximum number sum of paths from the top left to the bottom right
  • Longest ascending subsequence length

3. Existence

  • Take stone game, whether the first hand will win
  • Can you pick k numbers such that the sum is sum

See here, basically be an introduction! The next few articles will be a little more difficult than today’s topic, more content, welcome to pay attention to a wave!

Popular recommendations:

– what? OAuth2 is used by Github, Alipay and wechat, haven’t you ever used OAuth2?

– If you say the boundaries of dichotomy are too hard to handle, I’ll kill you

– JAVA Frequency limit for accessing the same interface from the same IP address (distributed (jingdong snapping up business) and actual use scenarios of token buckets

– Long word analysis: To get into a big factory, you have to know the BASICS of CPU caching

At the end of the article, I have compiled a recent interview data “Java Interview Customs Manual”, covering Java core technology, JVM, Java concurrency, SSM, microservices, database, data structure and so on. You can obtain it from GitHub github.com/Tingyu-Note… , more content to pay attention to my nuggets, in succession.