Preface:

Leetcode brushing is a performance of strength. As just brush more than ten small white, is really brush not move. It takes an hour or two to brush each question (no talent, after all), so mastering the skill is essential. I recently got a wulin unlearned ———— dynamic programming from my classmate. Pro test, efficient!! So I want to share it with you. Of course, I also hope that the masters can impart some of your extraordinary feats!

Dynamic programming

define

Dynamic programming (DP) : A method for solving complex problems by decomposing the original problem into relatively simple subproblems.

The basic idea behind dynamic programming is roughly as follows: if we want to solve a given problem, we need to solve its different parts (i.e., sub-problems), and then obtain the solution of the original problem according to the solutions of the sub-problems. In general, many subproblems are very similar, so the dynamic programming method tries to solve each subproblem only once, thus reducing the amount of computation: once the solution of a given stator problem has been calculated, it is stored in memory so that the next time the solution of the same subproblem is needed, it can be directly looked up in the table. This approach is particularly useful when the number of repeating subproblems increases exponentially with respect to the size of the input

application

Dynamic programming is often applied to problems related to overlapping subproblems and optimal substructural properties. The dynamic programming takes much less time than the naive solution

Example 1

Leetcode 70:

Suppose you’re climbing stairs. It takes n steps to get to the top. You can climb one or two steps at a time. How many different ways can you climb to the top?

Note: given n is a positive integer.

Example 1:

Input: 2

Explanation: There are two ways to climb to the top of the building.

  1. 1 order plus 1 order
  2. 2 order

Answer:

  1. Find out how many ways there are to climb the stairs, and there are two ways at a time. makearr[n]To climbnStep method, consider the last step may take one step, or may take two steps, climb to the firstnIt’s going to be the sum of how many times you climb one level plus how many times you climb two levels.

2. Arr [n-1] is the number of methods to reach n-1 order, and ARr [n-2] is the number of methods to reach n-2 order. So arr[n] will be equal to the sum of the number of methods to order N-1 and the number of methods to order N-2, that is, arr[n]= ARr [n-1]+ ARr [n-2]. 3. So on arr = arr [n – 1] [2] n – + arr [n – 3], arr = arr [n – 2] [n – 3] + arr [4] n -… Arr [2] = arr [1] + arr [0]. Did you lose school? That’s dynamic programming!

Divide n stairs into sections. And since we started from the 0th order, we can see that there is only one way to climb from the 0th order to the 0th order, that is, arr[0]=1, and there is only one way to climb from the 0th order to the 1st order, that is, climb one level, arr[1]=1. The code implementation is as follows:

 var climbStairs = function(n) {
    let arr=[]// Define array arr[] to store the number of methods
    arr[0] =1// The 0th order method is one
    arr[1] =1// The first order method is one
    for(let i=2; i<=n; i++){// Start from the second order
        arr[i]=arr[i-1]+arr[i-2]// The number of methods of order I
    }
    return arr[n]
};
Copy the code

Example 2- Difficulty escalation

Leetcode 368 questions

Answer [I] = answer[j] = answer[j] = answer[I]; Answer [I] % answer[j] == 0, or answer[j] % answer[I] == 0 if there are multiple valid solution subsets, return any one of them.

Example 1: Input: nums = [1,2,3] Output: [1,2] Explanation: [1,3] will also be considered the correct answer.

Example 2: input: nums = [1,2,4,8] output: [1,2,4,8]

Answer:

  1. judgeanswer[i]%answer[j]==0||answer[j] % answer[i] == 0

In this case it is easier to use two loops. If we can guarantee that when I < j, answer[I]< answer[j] is also valid, isn’t it a bit less complexity? Because only the returned array answer is required, the sorting of elements in the answer is not important, so numS can be sorted from small to large first.

  1. Save the result and compare the length of each result, returning the longest

If answer[I] is answer exactly divides the largest element in the array. If nums[j]%nums[I]==0, add nums[j] to answer array. Num [j] is the largest element in the divisible array. [j]%nums[I]==0? If the condition is true, put it into the answer array until the entire NUMS array is traversed. Finally, determine the length of each result array and return the longest one.

This is dynamic programming, dividing the NUMs into small arrays, then judging the conditions, and adding values to the small arrays.

 var largestDivisibleSubset = function(nums) {
    let answer=[] // Declare the answer array
    let answerlen=new Array(nums.length)// Define the answerLen array to receive the length of each result
    let maxIndx=0 // Declare the maxIndx variable and assign it to the subscript of the maximum value in the answer array each time
    nums.sort((a,b) = >(a-b))// Sort the numS array from smallest to largest
    
    for(let i=0; i<nums.length; i++){// I represents the subscript of nums[I], the largest element in the answer array
        
        answerlen[i]=1;// Each element must form at least one subset of itself
        
        for(let j=0; j<i; j++){// the index of the element before nums[I]
            
            if(nums[i]%nums[j]==0){
                
                answerlen[i]=Math.max(answerlen[i],answerlen[j]+1)
                // answerLen [I] specifies the length of the answer array when nums[I] is the largest element
                Answer [j]+1 nums[j] +1
                // It's possible that answerLen [j]+1 will be less than answerlen[I] (the length of the previous loop), and answerLen takes the maximum between them}}if(answerlen[i]>answerlen[maxIndx]){// set maxIndex to the index of the maximum number of elements in the answer array when the length of the answer array is the maximum
            maxIndx=i
        }
    }   
    Answerlen [maxIndex] answerLen [maxIndex]
    answer.push(nums[maxIndx])// Put the largest element into the array
    for(let i=nums.length-1; i>=0&&answerlen[maxIndx]>1; i--){if(answerlen[maxIndx]-1==answerlen[i]&&nums[maxIndx]%nums[i]==0) {// Not all elements preceding the largest element are divisible
            (nums[I] = nums[I] = nums[I] = nums[I])
            // This allows only elements less than nums[I] to be compared
            answer.push(nums[i])
            maxIndx=i
        }
    }
    return answer
};
Copy the code

conclusion

As a beginner, it is very important to master several martial arts secrets. I hope the knowledge I share will be of some help to you in the future. Also hope to read this article bigs can be generous to give advice, by the way a small hand praise 🙏.

Amway to teach me the skills of the students, nuggets of search users: eat eat eat, he wrote really good articles!