Yesterday, my colleague said that dynamic programming was very difficult, but I said no, it was very easy to understand, and my colleague was contemptuous, thinking that I was showing off my skills. So I asked a former colleague who had worked for six years, and he thought it was awesome. He also said that he had met a friend who knew dynamic planning.

I a day, said shocked, simply scared of my tremble tremble good yao. In that case, I must let you understand, let you also awesome awesome awesome.

In the topic, for example

Take China leetCode’s 121 questions “The best time to buy and sell stocks” for example, the title is as follows:

Given an array, its ith element is the price of a given stock on the ith day. If you only allow one trade (buy and sell one stock), design an algorithm to calculate the maximum profit you can make. Note that you can't sell a stock before you buy it. Example 1: input: [7,1,5,3,6,4] output: 5 explanation: buy on day 2 (stock price = 1) and sell on day 5 (stock price = 6), maximum profit = 6-1 = 5. Note that the profit cannot be 7-1 = 6, because the selling price needs to be greater than the buying price. Example 2: input: [7,6,4,3,1] output: 0 explanation: in this case, no transaction is completed, so the maximum profit is 0.Copy the code

So, first of all, dynamic programming is not a very efficient algorithm in this case, and this is a problem where even the brute force method is a little bit faster than dynamic programming, but I’m going to do this for dynamic programming, not for dynamic programming. It’s just that dynamic programming is easier.

Those who do not know dynamic programming may not know that dynamic programming almost always has routines, and the steps are as follows:

  1. Break the problem down into a single problem sheet
  2. Solve according to the results in the table

Step 1: Break down the question into a single question sheet

This is the most important part of dynamic planning, the quality of the demolition basically determines the quality of your dynamic planning to write, dynamic planning is an idea.

So this is a very simple problem, and we can break this down into a single problem, which is if I buy on this day, what day do I sell the most? For example 1 in the question, the price array is [7,1,5,3,6,4].

If I buy on the first day, what day do I sell the most? We can get a table that looks like this (no trading mark X) :

Buying time Buying price Price of a single day 7 1 5 3 6 4
— — Sell time The first day The second day On the third day The fourth day The fifth day On the sixth day
The first day 7 The degree of profit X – 6 2 – 4 – – 1 – 3

Fill in the form for the following reasons:

  • You can’t trade on the first day because you bought it on the first day
  • We bought it the first day at a price of 7, and the next day at a price of 1, so we sold it at a profit of minus 6.
  • We bought it on the first day at a price of 7, and on the third day at a price of 5, so we sold it at a profit of -2.
  • We bought it on the first day at a price of 7, and on the fourth day at a price of 3, so we sold it at a profit of -4.
  • We bought it on the first day at a price of 7, and on the fifth day at a price of 6, so we sold it at a profit of -1.
  • We bought it on the first day at a price of 7, and on the sixth day at a price of 4, so we sold it at a profit of -3.

Did someone say this isn't a violent solution? Well, the dynamic programming process for this problem does look a little bit like.

So according to the above rules, if we buy the next day, this table is not like this.

Buying time Buying price Price of a single day 7 1 5 3 6 4
— — Sell time The first day The second day On the third day The fourth day The fifth day On the sixth day
The second day 1 The degree of profit X X 4 2 5 3

So if I merge these two tables, it looks like this:

Buying time Buying price Price of a single day 7 1 5 3 6 4
— — Sell time The first day The second day On the third day The fourth day The fifth day On the sixth day
The first day 7 The degree of profit X – 6 2 – 4 – – 1 – 3
The second day 1 The degree of profit X X 4 2 5 3

So let’s complete the table, the third to fifth day buys, is that what it looks like?

Buying time Buying price Price of a single day 7 1 5 3 6 4
— — Sell time The first day The second day On the third day The fourth day The fifth day On the sixth day
The first day 7 The degree of profit X – 6 2 – 4 – – 1 – 3
The second day 1 The degree of profit X X 4 2 5 3
On the third day 5 The degree of profit X X X 2 – 1 – 1
The fourth day 3 The degree of profit X X X X 3 1
The fifth day 6 The degree of profit X X X X X 2 –
On the sixth day 4 The degree of profit X X X X X X

Because if you buy it on the sixth day, it’s already the last day, so you can’t sell it, so it’s all X’s.

Step 2: Solve according to the results in the table

In the previous step, I already listed the daily profit if I bought it on a certain day, so I broke it down into a single problem.

So if you look at the maximum profit, it’s easy to see, just look at the number that’s the largest.

Buying time Buying price Price of a single day 7 1 5 3 6 4
— — Sell time The first day The second day On the third day The fourth day The fifth day On the sixth day
The first day 7 The degree of profit X – 6 2 – 4 – – 1 – 3
The second day 1 The degree of profit X X 4 2 5 ⃣ ️ 3
On the third day 5 The degree of profit X X X 2 – 1 – 1
The fourth day 3 The degree of profit X X X X 3 1
The fifth day 6 The degree of profit X X X X X 2 –
On the sixth day 4 The degree of profit X X X X X X

Yes, emoji 5 is, so we can simply walk through the table and get the results out? Well, right

The last

But in general, the topic of dynamic planning is not so simple, usually in tabulation will involve a superposition problem, in accordance with the table calculation results are generally not simple traversal can be completed, but understanding the idea of dynamic planning should be no problem.

In my opinion, although dynamic programming has poor performance, it can make the problem more intuitive and make it easier to solve the problem. At the same time, the heterozygosity of the algorithm is not high, so it is convenient to solve every single problem of the distributed problem.

Best-time-to-buy-and-sell-stock.js