This paper introduces the sum of divide and conquer dynamic rule algorithm

This is the 18th day of my participation in Gwen Challenge

It is well known that divide-and-conquer algorithms and dynamic rule algorithms are the “favorites” of front-end interview. In our daily life, these two scenes are also relatively widely used. For example, divide and conquer is often used in scenarios such as binary tree flipping and quick search, while dynamic rule algorithms are often used in scenarios such as minimum coin change problems and knapsack problems.

In the following article, common scenarios for divide-and-conquer dynamic rules will be explained and some classic examples of LeetCode will be analyzed.

Divide and rule

1. What is divide and rule?

  • Divide and conquer is a method of algorithm design.
  • It divides a problem into several small problems similar to the original problem, solves the small problems recursively and combines the results to solve the original problem.

2. Application scenarios

  • Merge sort
  • Quick search
  • Binary search
  • Flip the binary tree
  • …

3. Scenario analysis: Merge sort and quicksort

(1) Scenario 1: Merge sort

  • Split: Splits an array down the middle.
  • Solution: Merge sort of two subarrays recursively.
  • Merge: Merges ordered subarrays.

(2) Scenario 2: Quicksort

  • Divide the array into two subarrays according to the base.
  • Solution: A recursive quicksort of two subarrays.
  • Merge: Merges two subarrays.

Dynamic rules

1. What are dynamic rules?

  • Dynamic rule is a method of algorithm design.
  • It decomposes a problem into overlapping sub-problems, which are solved repeatedly to solve the original problem.

When you look at this, a lot of people think, aren’t dynamic rules and divide-and-conquer solving the same problem? It’s not.

Note:

  • Dynamic rules solve overlapping subproblems.

  • Divide and conquer solves separate sub-problems.

This may seem a bit abstract, but I’ll go into more detail later in Point 3.

2. Application scenarios

  • Minimum coin change problem
  • Knapsack problem
  • Longest common subsequence
  • Matrix chain multiplication
  • …

3. Scenario analysis: Fibonacci sequence

The Fibonacci sequence is a typical mathematical problem. The Fibonacci sequence refers to a sequence like this:

The sequence starts with the third term, and each term is equal to the sum of the previous two terms. That is:


F i b o n a c c i [ n ] = { 0 . n = 0 1 . n = 1 F i b o n a c c i [ n – 1 ] + F i b o n a c c i [ n – 2 ] . n > 1 Fibonacci[n]= \begin{cases} 0,n=0 \\ 1,n=1 \\ Fibonacci[n-1]+Fibonacci[n-2],n>1 \end{cases}

So let’s tease out how the Fibonacci sequence uses the dynamic rule algorithm. There are two main points:

  • Define sub-problems: F(n)=F(n-1) + F(n-2);
  • Repeat: loop from 2 to n to execute the above formula.

Dynamic rules vs. divide and conquer

With that out of the way, let’s tease out the difference between dynamic rules and divide and conquer. Let’s start with a picture to show the difference.

As you can see, the Fibonacci sequence on the left is a decomposition of all problems into several overlapping problems, each with the same solution.

In the binary tree flipped on the right, the left and right subtrees are independent of each other, so the left and right subtrees need to be flipped first, and during the flipping process, they are flipped separately without interfering with each other. The left subtree works for the left subtree, and the right subtree works for the right subtree.

Unlike the Fibonacci sequence, where each layer is interdependent, nested on top of each other.

That’s the difference between dynamic rules and divide-and-conquer.

Common application of divide-and-conquer algorithm

Reinforce the divide-and-conquer algorithm with a few classic leetcode titles.

1, leetcode 374: Guess the size of the number

(1)

Here is a link to the original question

The rules of the guessing game are as follows:

  • Every round of the game, I take it from1 到 nPick a number at random. Please guess which number I chose.
  • If you’re wrong, I’ll tell you if your guess is bigger or smaller than my pick.

You can get the guess result by calling a predefined interface int guess(int num), which returns three possible values (-1, 1 or 0) :

  • - 1: The number I picked is smaller than you guessedpick < num 。
  • 1: The number I picked is larger than your guesspick > num 。
  • 0The number I picked is the same as your guess. A: congratulations! You guessed it!pick == num 。

Returns the number I selected.

(2) How to solve the problem

  • Binary search also has the characteristics of “division, solution and combination”.
  • Consider the option of divide and conquer.

(3) Steps to solve the problem

  • Divide: calculates the intermediate elements and splits the array.
  • Solution: Recursively performs binary search on larger or smaller arrays.
  • Merge: this step is not required because it is returned when found in the subarray.

(4) Code implementation

/** 
 * Forward declaration of guess API.
 * @param {number} num   your guess
 * @return 	            -1 if num is lower than the guess number
 *			             1 if num is higher than the guess number
 *                       otherwise return 0
 * var guess = function(num) {}
 */

/ * * *@param {number} n
 * @return {number}* /
let guessNumber = function(n) {
    
    const rec = (low, high) = > {
        if(low > high){
            return;
        }
        
       // 1. Calculate the middle element and split the array
        const mid = Math.floor((low + high) / 2);
        
        // 2. Compare with the guesses
        const res = guess(mid);
        
        // 3. Perform binary search recursively on larger or smaller arrays
        if(res === 0) {return mid;
        }else if(res === 1) {return rec(mid + 1, high);
        }else{
            return rec(low, mid - 1); }}return rec(1, n);
};
Copy the code

2, Leetcode 226: Reverse binary tree

(1)

Here is a link to the original question

Flip a binary tree.

(2) How to solve the problem

  • First flip the left and right subtrees, and then switch the subtrees.
  • It conforms to the characteristics of “divide, solve and combine”.
  • Consider the option of divide and conquer.

(3) Steps to solve the problem

  • Points: Get the left and right subtrees.
  • Solution: Recursively flip the left and right subtrees.
  • Combine: switch the flipped left and right subtrees to the root node.

(4) Code implementation

/** * Definition for a binary tree node. * function TreeNode(val, left, right) { * this.val = (val===undefined ? 0 : val) * this.left = (left===undefined ? null : left) * this.right = (right===undefined ? null : right) * } */
/ * * *@param {TreeNode} root
 * @return {TreeNode}* /
 var invertTree = function(root) {
    if(! root){return null;
    }
    return{
        //1. The value of the root node remains unchanged
        val:root.val,
        //2. Recursively transform the left and right subtrees
        left:invertTree(root.right),
        //3. Recursively transform the right and left subtrees
        right:invertTree(root.left)
    }
};
Copy the code

3, LeetCode 100: Same tree

(1)

Here is a link to the original question

Given the root nodes p and q of two binary trees, write a function to check whether the two trees are the same.

Two trees are considered identical if they are structurally identical and the nodes have the same value.

(2) How to solve the problem

  • Two trees: the root node has the same value, the left subtree has the same value, and the right subtree has the same value.
  • It conforms to the characteristics of “divide, solve and combine”.
  • Consider the option of divide and conquer.

(3) Steps to solve the problem

  • Points: Gets the left and right subtrees of two trees.
  • Solution: Recursively determine whether the left and right subtrees of two trees are the same.
  • Combine: Combine the above results, and if the root values are the same, the two trees are the same.

(4) Code implementation

/** * Definition for a binary tree node. * function TreeNode(val, left, right) { * this.val = (val===undefined ? 0 : val) * this.left = (left===undefined ? null : left) * this.right = (right===undefined ? null : right) * } */
/ * * *@param {TreeNode} p
 * @param {TreeNode} q
 * @return {boolean}* /
let isSameTree = function(p, q) {
    if(! p && ! q){return true;
    }
    P tree and Q tree exist at the same time; * 2. Each time a node is traversed, the node values of both trees exist; * 3. Recursive left subtree, comparing the value of each node; * 4. Recursive right subtree, comparing each node value. * /
    if(p && q && p.val === q.val &&
        isSameTree(p.left, q.left) &&
        isSameTree(p.right, q.right)
    ){
        return true;
    }
    return false;
};
Copy the code

Leetcode 101: Symmetric binary trees

(1)

Here is a link to the original question

Given a binary tree, check whether it is mirror – symmetric.

(2) How to solve the problem

  • To: Whether the left and right subtrees are mirrored.
  • It is decomposed into whether the left subtree of tree 1 and the right subtree of tree 2 mirror each other, and whether the right subtree of tree 1 and the left subtree of tree 2 mirror each other.
  • In line with the characteristics of “divide, solve and combine”, the choice of divide and conquer is considered.

(3) Steps to solve the problem

  • Points: Gets the left and right subtrees of two trees.
  • Solution: Recursively determine whether the left subtree of tree 1 and the right subtree of tree 2 mirror each other, and whether the right subtree of tree 1 and the left subtree of tree 2 mirror each other.
  • Combined: If the above is true and the root values are the same, the two trees are mirror images.

(4) Code implementation

let isSymmetric = function(root){
    if(! root){return true;
    }

    const isMirror = (l, r) = > {
        if(! l && ! r){return true;
        }

        * 1. The left and right subtrees exist at the same time; * 2. The root nodes of the left and right subtrees are the same; * 3. The left node of the left subtree mirrors the right node of the right subtree; * 4. The right node of the left subtree mirrors the left node of the right subtree */
        if(l && r && l.val === r.val &&
            isMirror(l.left, r.right) &&
            isMirror(l.right, r.left)
        ){
            return true;
        }
        return false;
    }
    return isMirror(root.left, root.right);
}
Copy the code

Common application of dynamic rule algorithm

Several classic leetcode topics are cited to enhance dynamic rule algorithms.

Leetcode 70: Take the stairs

(1)

Here is a link to the original question

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.

(2) How to solve the problem

  • Climbing to the NTH step can be done by climbing 1 step on the n-1 step, or 2 steps on the n-2 step.
  • F of n is equal to F of n minus 1 plus F of n minus 2.
  • Use dynamic rules.

(3) Steps to solve the problem

  • Define the subproblem: F(n) = F(n-1) + F(n-2).
  • Repeat: loop from 2 to n to execute the above formula.

(4) Code implementation

 /* * @param {number} n * @return {number} */
// Array methods
var climbStairs = function(n) {
    if(n < 2) {return 1;
    }
     // Record how many steps can be taken in order 0 and 1
    const dp = [1.1];
    // Start at level 2 and continue until level 5
    for(let i = 2; i <= n; i++){
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[n];
};
Copy the code

If DP is recorded by a one-dimensional array, the time complexity and space complexity are O(n), so the efficiency is still low.

So what can be done to reduce its complexity?

You can take a variable approach. As we can see from the above code, dp is stored in an array and grows linearly. So at this point, we can consider converting this one-dimensional array into a single variable, making constant substitutions to reduce space complexity.

The following code to achieve again.

let climbStairs2 = function(n){
    if(n < 2) {return 1;
    }
    // Define a variable to record the number of steps at n-2
    let dp0 = 1;
    // Define a variable to record the number of steps when n - 1
    let dp1 = 1;
    for(let i = 2; i <= n; i++){
        const temp = dp0;
        // after each iteration, let dp0 point to the next value, i.e. Dp1
        dp0 = dp1;
        // Set dp1 to the value of the next number, i.e., the sum of the first two numbers, i.e., dp1 and dp0
        dp1 = dp1 + temp;
    }
    return dp1;
}
Copy the code

As you can see from the code above, without arrays or arrays that grow linearly like matrices, the space complexity becomes O(1).

2, LeetCode 198: Robbery

(1)

Here is a link to the original question

You are a professional thief, planning to rob the houses along the street. There is a certain amount of cash hidden in each room, and the only constraint on your ability to steal is that adjoining houses are equipped with interconnected security systems that will automatically alert the police if two houses are broken into on the same night.

Given an array of non-negative integers representing the amount of money stored in each house, calculate the maximum amount of money you can steal in one night without setting off the alarm.

(2) How to solve the problem

  • F (k) = the maximum amount of money that could be stolen from the previous K houses.
  • Ak is the amount of money for the KTH house.
  • F (k) = Max (f(k – 2) + Ak, f(k – 1).
  • Consider using dynamic rules.

(3) Steps to solve the problem

  • Define the subproblem: f(k) = Max (f(k-2) + Ak, f(k-1)).
  • Repeat: loop from 2 to n to execute the above formula.

(4) Code implementation

/ * * *@param {number[]} nums
 * @return {number}* /

let rob1 = function(nums) {
    if(nums.length === 0) {return 0;
    }
    // The amount of money that can be hijacked by the first 0 houses and the first 1 house
    const dp = [0,nums[0]].for(let i = 2; i <= nums.length; i++){
        dp[i] = Math.max(dp[i - 2] + nums[i - 1], dp[i - 1]);
    }
    return dp[nums.length];
};
Copy the code

Similarly, if DP is recorded in a one-dimensional array, the time complexity and space complexity are O(n), so the efficiency is still low.

At this time, we can use the single variable method to reduce the space complexity.

The following code to achieve again.

let rob2 = function(nums) {
    if(nums.length === 0) {return 0;
    }
    let dp0 = 0;
    let dp1 = nums[0];
    for(let i = 2; i <= nums.length; i++){
        const dp2 = Math.max(dp0 + nums[i - 1], dp1);
        dp0 = dp1;
        dp1 = dp2;
    }
    return dp1;
};
Copy the code

And the space complexity of course becomes order 1.

Leetcode 62: Different paths

(1)

Here is a link to the original question

A robot is located in the upper left corner of an M x N grid (the starting point is marked “Start” in the figure below).

The robot can only move one step to the right or down at a time. The robot attempts to reach the lower right corner of the grid (marked “Finish” in the image below).

How many different paths are there?

(2) How to solve the problem

  • You can only move one step down or one step to the right, so you want to go to (I,j), and if you go down one step, you go from (I -1,j); If I take a step to the right, I go from I,j-1.
  • F (I, j) = f(I -1, j) + f(I, j-1).
  • Use dynamic rules.

(3) Steps to solve the problem

  • Define the subproblem: f(I, j) = F (i-1, j) + f(I, j-1).
  • Repeat: loop from 2 to n to execute the above formula.

(4) Code implementation

let uniquePaths = function(m, n){
    const f = new Array(m).fill(0).map(() = > new Array(n).fill(0));
    for(let i = 0; i < m; i++){
        // add 1 to the first column
        f[i][0] = 1;
    }
    for(let j = 0; j < n; j++){
        // fill the first row with 1
        f[0][j] = 1;
    }

    for(let i = 1; i < m; i++){
        for(let j = 1; j < n; j++){
            f[i][j] = f[i - 1][j] + f[i][j - 1]; }}return f[m - 1][n - 1];
}
Copy the code

V. Concluding remarks

Divide-and-conquer dynamic rule algorithm in the front-end application is quite a lot, especially in the interview or written test will often appear this kind of questions, we can continue to brush this kind of Leetcode questions in addition, do more slowly will be able to draw a conclusion ~

  • Pay attention to the public number Monday laboratory, the first time to pay attention to learning dry goods, more interesting columns for you to unlock ~
  • If this article is useful to you, be sure to like it and follow it
  • See you next time! 🥂 🥂 🥂