preface

In the last article dynamic programming, we first introduced the Fibonacci example into dynamic programming, and then analyzed the three main properties of dynamic programming with the help of the change example, namely:

  1. Overlapping subproblem
  2. Optimal substructure
  3. State transition equation

But dynamic programming is more than that.

In today’s article, let’s dive into the nature of dynamic programming.

Now that we want to get to the bottom of dynamic programming, the inevitable question is:

What’s the difference between recursive, greedy, mnemonic search and dynamic programming?

  • Dynamic programming in recursion: Is it simply space for time? No, the Fibonacci sequence nicely refutes that idea.

  • Dynamic programming for Greed: Is it just greed enhanced? No, the change example also contradicts this view.

So what is the core of dynamic programming?

To answer this question, we might as well answer the following question:

Which problems are suitable for dynamic programming? How to identify the DP solvable problem?

I believe that when we recognize which problems can be solved with DP, we will naturally find the difference between DP and other algorithmic ideas, which is the core of dynamic programming.

Dynamic programming core

First of all, we should make it clear that dynamic programming is only suitable for a certain kind of problems, only a solution to a certain kind of problems.

So what is this “problem of a certain kind”?

Before we get to that, it’s important to understand a little bit about the nature of computers.

Why is a computer based on the Von Neumann architecture essentially a state machine? Because the CPU has to deal with memory to do calculations.

Because the data is stored in memory (registers and external disks are the same nature), the CPU does not calculate the air without data. Therefore, memory is used to store state (data), all the data currently stored in memory constitute the current state, CPU can only use the current state to calculate the next state.

When we use computers to deal with problems, we are thinking about how to store states in variables and how to transfer them from one variable to another, from one current state to the next.

Based on these, we have obtained two main indicators to judge the merits and demerits of the algorithm:

  • Spatial complexity: The state of storage necessary to support calculations

  • Time complexity: the number of steps from the initial state to the final state

If that’s not clear enough, let’s use Fibonacci’s example:

  • To compute the current f(n), all you need to know is f(n-1) and f(n-2).

That is:

  • To compute the current state f(n), you only need to compute the states F (n-1) and f(n-2).

That is, the current state is only related to the first two states, so for spatial complexity: we only need to save the first two states.

And that’s why dynamic programming is not just about space and time, because it’s all about states.

The calculation time required to transfer from one state to another is also constant, so the total time complexity of linearly increasing states is also linear.

This is the core of dynamic programming, namely:

Definition of states and transitions between states (definition of equations of state).

So how do you define “states” and “transitions between states”?

Let’s introduce wikipedia’s definition:

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

By breaking up the problem and defining the relationship between its states and states, the problem can be solved recursively (or divide-and-conquer).

On paper to talk about shallow, let’s look at a very classic example.

Longest increasing subsequence

This is LeetCode problem 300.

Given a sequence of length N, find the length of the longest ascending (increasing) subsequence (LIS) of the sequence.

Example 1:

Input: nums = [10,9,2,5,3,7,101,18] output: 4 explanation: the longest increasing subsequence is [2,3,7,101], so length is 4Copy the code

Example 2:

Input: nums = [0,1,0,3,2,3] output: 4 explanation: the longest increasing sequence is [0,1,2,3], so the length is 4Copy the code

How do we define states and transitions between states?

I. Definition of state

First we should split the problem, that is, define the sub-problem of the problem.

So, let’s redefine the question:

Given a sequence of numbers of length N,

Set FkIs: the length of the longest increasing subsequence ending in the KTH term of a given sequence

O F1To FNThe maximum size of the

Is this definition the same as the original problem?

Obviously these are equivalent, but obviously the second way we defined it, we found the subproblem.

For F k, F one up to F k minus one are all subproblems of F k.

The F k of this new problem is called the state.

F k is the length of LIS at the end of the KTH term in the sequence, which is the definition of the state.

Definition of state transition equation

After the states are defined, the relationship between the states is called the state transition equation.

This problem is defined by F and K:

Set FkIs: the length of the longest increasing subsequence ending in the KTH term of a given sequence

Thinking, how do you transfer between states?

Remember we talked about splitting no, we can do the same thing here, we can split the data.

What if there’s only one number in the sequence? Then we should return 1(we found the state boundary case).

Then we can write the following state transition equation:

F1 = 1

Fk = max ( Fi1, + 1 | I ∈ (k – 1)) (k > 1)

That is, the length of LIS ending with the KTH term is Max {LIS ending with the i-th term + 1}, and the i-th term is smaller than the k-th term

Everyone understand, is it so ~

Remember what we did?

  1. We redefined the problem (subproblem) (state definition) by splitting the problem;
  2. Through the definition of the state, combined with the boundary of the state, we write the definition of the transition between the states, namely the state transition equation.

I wrote down the state transition equation, and I can say that at this point, the idea at the heart of the dynamic programming algorithm has been expressed.

The rest is just a matter of memorizing the recursion.

Now let’s try to write code.

code

First we define the dp array:

int[] dp = new int[nums.length];
Copy the code

(Note that the size of the dp array is slightly different from that of the change example in the previous article, that is, there is no +1 here, you can click here to read the previous article to understand it more carefully.)

So the meaning of dp array here is:

Dp [I] holds the length of the longest incrementing subsequence up to the I bits of a given array.

So what is our initial state?

We know that the boundary of the state is:

F1 = 1

  • That is, if the data has only one digit, it should return 1;
  • When the number of data is greater than 1, return 1 if there is no second increment in the entire sequence.

So, in the initial state we assign 1 to each position in the DP array.

Arrays.fill(dp, 1);
Copy the code

We then iterate from the first element of the given array, writing out the outer for loop:

for(int i = 0; i < nums.length; i++){ ...... }Copy the code

What do we do when we go to something in our outer layer?

We have to find out if there is anything smaller than that before the outer element, and if there is, then we update the dp[I] of the outer element.

If something has a smaller number before it, doesn’t that constitute an increasing subsequence?

So we can write the inner for loop:

for (int j = 0; j < i; j++) {
    Dp [I] = dp[j] + 1 if nums[I] = dp[j] + 1
     if (nums[j] < nums[i]) {
         // Since nums[I] can be preceded by multiple numbers smaller than it, i.e., multiple combinations, we take the largest group and place it in dp[I]
          dp[i] = Math.max(dp[i], dp[j] + 1); }}Copy the code

At the end of the two-layer loop, the maximum increment subsequence length before the corresponding element position is stored in dp[] array. We just need to traverse dp[] array to find the maximum value, and then we can get the maximum increment subsequence length of the entire array:

 int res = 0;
 for(int k = 0; k < dp.length; k++){
      res = Math.max(res, dp[k]);
 }
Copy the code

This problem code is finished, the following post the complete code:

class Solution {
  public int lengthOfLIS(int[] nums) {
      if(nums.length < 2) return 1;
      int[] dp = new int[nums.length];
      Arrays.fill(dp,1);
      for(int i = 0; i < nums.length; i++){for(int j = 0; j < i; j++){if(nums[j] < nums[i]){
            dp[i] = Math.max(dp[i],dp[j] + 1); }}}int res = 0;
      for(int k = 0; k < dp.length; k++){ res = Math.max(res,dp[k]); }returnres; }}Copy the code

This two-layer for loop is basically the same as the code for changing change before.

The only difference is the judgment condition of the inner for loop and the expression of the state transition equation (how to update DP []), which is the essence of dynamic programming.

summary

There are many misconceptions and misconceptions about dynamic programming, the most common of which is probably that it is space for time, and the difference between it and greed.

Hopefully these two articles on dynamic programming will help you dispel these misconceptions and better understand the nature of dynamic programming, states and equations of state.

Of course, only these two articles want to explain dynamic programming is far from enough, so the following will specifically explain some typical problems, such as backpack problem, stone game, stock problem and so on, hoping to help you to avoid some detdetments on the road of learning algorithms.

If you have any algorithms or problem types you’d like to know, feel free to let me know in the comments section, and we’ll see you next time!