Since I understand the idea of dynamic planning, I have opened the door to a new world

Preface

Today I learned the dynamic programming algorithm , Sorted out some big guy's notes . I decided to write a blog , For students who want to learn dynamic programming algorithm , Let me show you what dynamic planning is .

brief introduction

Dynamic programming （Dynamic Programming）( hereinafter referred to as DP) The core idea of the algorithm is ： Divide big problems into small ones to solve , So as to obtain the optimal solution step by step . Solve complex problems by decomposing the original problem into relatively simple problems .

Dynamic programming is not a specific algorithm , It's an idea ： To solve a given problem , We need to solve its subproblem , Then the solution of the original problem is obtained according to the sub problem .

Some people may say that this is similar to divide and conquer , The difference is that the solution of divide and conquer algorithm does not depend on the subproblem ,DP It depends on the solution of the subproblem .

Optimal substructure

What is stipulated is the relationship between the original problem and the sub problem

DP What we need to solve is the optimal solution of some problems , That is to find the best one from many solutions to the problem . When we solve the optimal solution of a problem , We divide it into sub problems , Transform bits to solve the optimal solution of the subproblem , Finally, the final result is obtained by combining the optimal solution of the subproblem . In other words, the optimal solution of a problem is determined by the optimal solution of its subproblems .

Repeat the question

What is stipulated is the relationship between sub problems

When we recursively find the optimal solution of each subproblem , There may be some Repeated sub problems , If it's just ordinary recursion , There may be many repeated calculations , and DP It can ensure that each overlapping subproblem will be solved only once . When there are many repeated questions ,DP It can reduce a lot of repeated calculations .

for example ： Fibonacci problem ： seek f（5）

  			f(5)
  		  /      \
  		f(4)	 f(3)
  	   /	\	 /   \
  	f(3)   f(2)f(2)  f(1)
    /  \
  f(2) f(1)

f（3） It's double counting , about DP For example, we can build tables to store the answers to sub questions , To avoid double counting

Optimal substructure and repeated subproblem

1. There is a choice in the scheme of proving the problem , Leave one or more sub questions after selection
2. Recursive description of design subproblems
3. It is proved that the optimal solution of the original problem includes the optimal solution of all subproblems
4. Prove that the subproblems overlap （ It's not necessary , But if there is no overlap, the efficiency is the same as that of ordinary recursion ）

Example ： Deepen the understanding

Force to buckle 300 Question longest increasing subsequence

Give you an array of integers nums, Find the length of the longest strictly increasing subsequence .
Subsequence Is a sequence derived from an array , Delete （ Or do not delete ） Elements in an array without changing the order of the rest . for example ,[3,6,2,7] It's an array [0,3,1,6,2,2,7] The subsequence .

for example ：

Ideas ：

Reduce one at a time ： remember f(n)f(n) In order to nn The longest subsequence at the end of the number , Reduce one at a time , Divide the original problem into f(n-1)f(n−1), f(n-2)f(n−2), …, f(1)f(1), common n - 1n−1 Subproblem .n - 1 = 7n−1=7 The sub questions and answers are as follows ：
[10, 9, 2, 5, 3, 7, 101] -> [2, 5, 7, 101]
[10, 9, 2, 5, 3, 7] -> [2, 5, 7]
[10, 9, 2, 5, 3] -> [2, 3]
[10, 9, 2, 5] -> [2, 5]
[10, 9, 2] -> [2]
[10, 9] -> [9]
[10] -> [10]

There has been a 7 After the optimal solution of the subproblem , We can find a combination method to get the optimal solution of the original problem ：f(6)f(6) Result [2,5,7], 7 < 187<18, At the same time, the length is also f(1)~f(7) in , Ending less than 18 The longest result .f(7) Although the length is 4 Than f(6) Long , But the ending is no less than 18 Of , Can't be combined into the solution of the original problem . The final result is the number of the longest sequence .

The above combination can be written into a formula , The state transition equation ：
f(n)=maxf(i)+1 among i<n And a[i]<a[n]

Dynamic programming solution

[10, 9, 2, 5, 3, 7, 101] -> [2, 5, 7, 101]
[10, 9, 2, 5, 3, 7] -> [2, 5, 7]
[10, 9, 2, 5, 3] -> [2, 3]
[10, 9, 2, 5] -> [2, 5]
[10, 9, 2] -> [2]
[10, 9] -> [9]
[10] -> [10]

From here we can see that -> How to get the sequence on the right ？
We look from the bottom up

1. The first is 10, So the length of the longest sequence is recorded as 1
2. The second is 9, It has only 10 And 9 < 10 , So the length of the current subsequence is still 1
3. The third number is 2, Similarly, the previous numbers are larger than it, so the current subsequence length is still 1
4. The fourth number is 5, We have to 2 Smaller than his , And the length of the subsequence of two is 1, add 5 So the length becomes 2
5. The fifth number is 3, We have to 2 Smaller than his , And the length of the subsequence of two is 1, add 3 So the length becomes 2
6. The sixth number is 7, Obviously, the front 2,5,3 All ratio 7 Small , So we add the longest sequence smaller than it ,3 perhaps 5, So to 7, His sequence length becomes 3.
7. The seventh digit 101, Similarly, the longest sequence smaller than him in front is 3, Plus its own length is 4
8. Last digit 18,, The longest sequence smaller than him in front is numbers 7 The length of one line of is 3, So its subsequence is 4
9. The final longest subsequence is the longest of all subsequences . by 4

 public static int lengthOfLIS(int[] nums) {
    
        if (nums.length==0){
    
            return 0;
        }
        // Define an equal length array   To store the sequence length 
        int[] arr = new  int[nums.length];
        arr[0] = 1;
        // The shortest sequence length is 1
        int ans = 1;
        // Used to calculate the length of subsequence 
        for (int i = 1;i<nums.length;i++){
    
            // The shortest is oneself 
            arr[i] = 1;
            // Look for the front than i Small number 
            for (int j =0;j<i;j++){
    
                // If you find a value smaller than the current value   be +1 Is that when  i  The longest sequence before 
                if (nums[j]<nums[i]){
    
                    // Compare all the smaller ones   Find the longest 
                    arr[i] = Math.max(arr[j]+1,arr[i]);
                }
            }
            // When to exit for loop   Description has found the containing nuns[i] The longest sequence of   to update ans
            ans = Math.max(ans,arr[i]);
        }

        // Return the result 
        return ans;
    }

DP It can be gradually promoted by filling in the form , So as to obtain the optimal solution

For recursive solution , I will not , Ha ha ha ha