What is dynamic programming?

I quote a passage from Leetcode, which I think is very authoritative, and I will take you through dynamic programming in real life.



Are you confused? That’s right. When I first got into dynamic programming, I got stuck for a long time. However, dynamic programming is not so difficult as long as we understand the following problems. (THREE dimensional four dimensional DP difficult to doubt life QAQ)

  1. Definition of state
  2. State transition equation (Mathematical induction)
  3. Initial conditions and boundaries

Still a little confused? That’s right. Let me elaborate.

Definition of state

And the definition of state, you’re just looking for the conditions that they give you, the constraints. Take, for example, the classic climbing stairs.

First of all, we collected the problem restrictions, one is that you can only climb one step at a time, or two steps at a time. The other is n steps to reach the roof; So our definition of state must depend only on these two conditions. It’s not nonsense, it’s not nonsense, sometimes one of the key things to solve a problem is to get the definition of state right;

So what’s the definition of this state? Obviously different ways to climb the n steps to the top.

Dp = different ways to climb to the top

State transition equation (Mathematical induction)

Transfer equation, is also one of the difficulties of DP, or continue to take climbing stairs as an example; In fact, THE most difficult dp is the first two points; Once the definition of state and the state transition equation are defined, dp is solved.

In fact, the transition equation, which is mathematical induction, sounds pretty fancy, right? It’s all about finding patterns.

The key is how do you find patterns? Teach a man to fish rather than to fish him.

Directly according to the solution of the problem, divided into sub-problems, smaller problems to think; Like climbing stairs, n steps? I’m sure those of you who haven’t been exposed to DP will be confused, so don’t be afraid, we’ll start thinking about small problems, get results, and then recursively derive laws, which are state transition equations;

  • N =1, that’s 1
  • N is equal to 2, which is 2
  • N is equal to 3, which is 3
  • N is 4, so it’s 5
  • .

Take a closer look at the data above. As the size of the problem gets bigger, so does the result. What’s the pattern? If you are observant, you will certainly notice that f(n) = f(n-1) + f(n-2), which is the most familiar Fibonacci sequence problem. Here, the state transition equation is f(n) = f(n-1) + f(n-2) {n > 2}

Initial conditions and boundaries

We put the state and the state transition equation was determined, the definition of the initial conditions is very simple, observe the state transition equation directly meet the conditions of the starting value, is n > 2, when meet this condition, the formula is set up, do not meet the conditions of formula, is the initial conditions or boundaries, that is, when n < = 2 results, That’s the initial conditions; We can easily figure out that f(1) = 1, f(2) = 2; Sometimes dp, which is more difficult, needs to be determined by the state transition equation, as explained later.

Code template

Now that we have the three conditions for DP to determine, we can write code based on those three conditions

var climbStairs = function(n) {    
  // State: dp = Different ways to climb to the top
  // Boundary: fn(1) = 1, fn(2) = 2
  // Fn (n) = fn(n-1) + fn(n-2)
  if(n < 3) return n    
  let fn_1 = 1    
  let fn_2 = 2    
  let res = 0   
  for(let i = 3; i <= n; i++){ 
    res = fn_1 + fn_2  
    fn_1 = fn_2        
    fn_2 = res  
  }   
  return res
};Copy the code

Classic stock series problems

When you fully understand the stock series of problems, you are really getting started with dynamic programming problems. Before this, there is a great god’s article written very good, but it is the Java version, I also found a small mistake in the process of learning, struggling for a long time, after understanding this article, to make a summary of dynamic programming learning. I hope you can carefully read the original text first, it is very long, you have to be patient to understand the problems, do not bother with the details, I will lead you to solve these details, a real introduction to dynamic planning. The original link

Stock issue status definition

I assume that you have read the original text, probably understand what the author is talking about, first review the status map, some friends will certainly ask? How did he get this map of state definitions? And up the stairs, as I said, they’re drawn based on the constraints of the problem.



  • 1 represents holding the stock, which can only be rest, or sell the stock
  • 0 indicates that no stock is held. You can only choose REST or buy to buy the stock

The above two points are the most critical definition of the state. Combined with the number of times k can be traded and the stock price on the ith day, the specific definition of the state can be as follows:

  • Dp [I][K][1] : Today is the I day, I now hold the stock, so far the most k transactions.
  • Dp [I][K][0] : Today is the I day, I do not hold stocks in hand, so far the most k transactions.

Obviously, the final answer we want to find is dp[n-1][K][0], which is the last day, the maximum number of trades allowed, the maximum amount of profit. Why not dp[n-1][K][1]? Since [1] means still holding stock and [0] means the stock has been sold, it is obvious that the profit of the latter must be greater than the former.

State transition equation (Mathematical induction)

The most critical step is also one of the difficulties, but for the state transition equation, we can obtain the transition according to the definition of the state. By carefully observing the state transition diagram above and the operation of buying and selling stocks, we can obtain two state transitions of holding stocks or not holding stocks. If you still don’t understand, look back at the status chart for buying and selling.

  1. Do not own stock: did not have before, can rest; Or I had it before and I’m selling it now.
  2. You already own the stock, you already own it, you can rest,Or I didn’t own it before and I buy it now.

According to this state transition, we can get the state transition equation, which is a general formula by mathematical induction, [Here we should pay attention to the problem that selling the stock will make a profit and buying the stock needs to pay the cost]. Why k minus 1? Because when we buy a stock the number of trades goes down by 1.

  1. dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1] + prices[i])

  2. dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0] – prices[i])

So now, the transition equation is written out, and the hard part is to think about the state diagram of buying and selling stocks, and get the transition equation from the state machine, but I think it’s all a matter of proficiency, you just have to understand the nature of dp, and the rest is just practice.

Initial conditions and boundaries

The initial conditions and boundaries of the stock problem are going to be a little bit cryptic, not as straightforward as climbing stairs. And as I said, the hard ones we can plug in directly from the transition equation, and we can say, let’s try it out.

  • dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1] + prices[i])
  1. dp[0][k][0] = max(dp[-1][k][0], dp[-1][k][1] + prices[i]) { i = 0 }
  2. Dp [-1][k][0] = 0; dp[-1][k][0] = 0;
  3. Dp [-1][k][1] = dp[-1][k] Since not owning is 0, we’re going to use minus Infinity for the value of not owning the stock to begin with, minus Infinity
  4. So dp [I] [k] [0] = Max (0 – Infinity + prices [I]) = 0
  • dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0] – prices[i])
  1. dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0] – prices[i]) { i = 0 }
  2. Similarly, dp[i-1][k][1] is -infinity, dp[i-1][K-1][0] is 0
  3. So dp [I] [k] [1] = Max (- Infinity, 0 – prices [I]) = – prices [I]

So that gives us the initial conditions and the boundary values, when I minus 1 is equal to lambda minus 1

  • dp[-1][k][0] = 0
  • dp[-1][k][1] = –prices[0]

When k= 0, we haven’t traded yet, it’s the same thing

  • dp[i][0][0] = 0

  • dp[i][0][1] = –prices[0]

Code template

  • Let dp[n][k+1][2], n, k+1, 2 be the number of elements in the current dimension array. Instead of k, n minus 1. Because dp requires recursion of initial values, we take one more element.
  • I is the number of days, m is the maximum number of transactions, and 0 or 1 is the transaction status. And 0 <= I < n, 1 <= m <= k
  • Why do some state enumerations come forward? Some are the other way around, right? You can do either, you just have to remember, when you’re walking through, the states you want have to be computed; The end point of the traversal must be the location where the results are stored.

const maxProfit = function(k, prices) {// Number of trading daysletn = prices.length; // Maximum number of transactions, k does not affect the state transition equationlet maxTime = k;
    if(n == 0){
        return0; } // initialize the 3d array // If k does not affect the state transition equation, this initialization is removedlet dp = Array.from(new Array(n),() => new Array(maxTime+1));
    for(leti = 0; i < n; i++){for(letr = 0; r <= maxTime; r++){ dp[i][r] = new Array(2); }} // If problem k does not affect the state transition equation, then only the two-dimensional array // is requiredletdp = Array.from(new Array(n),() => new Array(2)); // enumerate recursionfor(leti = 0; i < n; I++){// if k does not affect the state transition equation, the inner loop is removedfor(letk = maxTime; k >= 1; k--){if(I == 0){// Boundary condition processingcontinue; } // Recursive formula, The above analysis, the state transition equation of dp [I] [k] [0] = math.h Max (dp [I - 1] [k] [0], dp [k] [I - 1] [1] + prices [I]) dp [I] [k] [1] = math.h Max (dp [I - 1] [1], [k] Dp [i-1][k-1][0] -prices [I])}} // A result is displayedreturndp[n-1][maxTime][0]; // If k does not affect the state transition equation, return this resultreturn dp[n-1][0];
};Copy the code

Six stock questions in a second

The best time to buy and sell stocks. The best time to buy and sell stocks. 714. The best time to buy or sell stocks includes the freeze period

The first line of



The name of the second

122. The best time to Buy and sell stocks II



The third way




The fourth

188. The best time to buy and sell stocks IV

The fifth



Sixth,

714. The best time to buy or sell stocks includes fees



conclusion

Dp problems need more practice, simple one-dimensional and two-dimensional is ok, not difficult, three-dimensional thinking is a test of proficiency and mathematical modeling abstract ability, we have to admit that some are gifted players, ordinary people, practice more good.

In fact, the biggest benefit of practicing algorithms is to improve coding ability. Half a year ago, I did not know the algorithm at all, and occasionally got stuck in writing business. Before, I met a business problem of permutation and combination and was completely confused. After half a year’s improvement in thinking, I can complete the business code in a cutting style, and the code writing is much better than before. For a bit more difficult, a bit more complex component packaging, can also be packaged well. You can even wrap your own UI library. So, algorithms are really useful, the best choice for a solid coding background.

In addition, recommended reading god algorithm cheat sheet, links.