preface

The previous series of articles shared various data structures and algorithm implementation, this article will share some algorithm design techniques: divide and conquer, dynamic programming, using these techniques to solve problems, improve their problem solving ability, you are welcome to interested developers read this article.

Divide and conquer

In the sorting algorithm shared earlier, merge sort is a divide-and-conquer algorithm. Divide and conquer is a method in algorithm design. It divides a problem into several small problems similar to the original problem, solves the small problems recursively, and then merges the solutions to solve the original problem.

Algorithm thought

This approach can be broken down into three parts:

  • Decompose, divide the original problem into many sub-problems.
  • Solve, a recursive algorithm that returns a solution to a subproblem.
  • Combine and combine the solutions of these sub-problems to obtain the solution of the original problem.

Instance to explain

In the previous search algorithm, we implemented binary search in an iterative way, and then we implemented it through divide-and-conquer. We apply the above algorithm idea, the logic is as follows:

  • Decompose: Computes mid and searches for the smaller or larger half of the array
  • Solution: Search for values in the smaller or larger half
  • Merge: Here we return the index value we found directly, so there is no need to merge

Next, let’s look at the implementation idea:

  • Since we need recursion, we need two functions:binarySearchR 和 binarySearchRecursive, the former is used to expose developers to calls, and the latter is a divide-and-conquer algorithm.

  • Let’s start by looking at what’s exposed to developersbinarySearchRRealization idea:
    • Calls the sort method to sort the sorted array
    • Declare two auxiliary variableslwoandhighAnd the values are respectively0andarray.length - 1, used to define the split point from where in the array to where to perform divide-and-conquer.
    • callbinarySearchRecursiveFunction that returns the result.
  • Now, let’s look at the divide-and-conquer functionbinarySearchRecursiveRealization idea:
    • It takes four arguments: a partitioned arrayarrayThe target value of,value, array start point decomposition pointlow, array end decomposition pointhigh
    • If low <= high, compute the intermediate indexmid, extract the median valueelement. Perform the following judgments:
      • ifelement < value, represents that the target value is to the right of the median value, then frommid + 1The position starts to decompose the array tohighThe location performs divide-and-conquer
      • ifelement > value, represents that the target value is to the left of the median value, then fromlowThe position starts to decompose the array tomid - 1The location performs divide-and-conquer
      • Otherwise it iselement ===value, target value found, return mid.
  • Otherwise,low > high, the target value is not in the array, returnsnull.

Next, let’s translate the above ideas into code:

// Binary search: recursive implementation
    binarySearchR(): number | null {
        this.sort.quickSort();
        const low = 0;
        const high = this.array.length - 1;
        return this.binarySearchRecursive(this.array, this.target, low, high);
    }
    /** * binary search recursive helper function *@param Array Decomposed array *@param Value Target value *@param Low The initial decomposition point of the array *@param The end of the high array is split by */
    binarySearchRecursive(array = this.array, value = this.target, low: number.high: number) :number | null {
        if (low <= high) {
            // Compute the intermediate index
            const mid = Math.floor((low + high) / 2);
            // Get the intermediate value
            const element = array[mid];
            if (this.compareFn(element, value) === Compare.LESS_THAN) {
                // Element < value finds the high position in the array mid+1, to the right of the middle value
                return this.binarySearchRecursive(array, value, mid + 1, high);
            } else if (this.compareFn(element, value) === Compare.BIGGER_THAN) {
                // Element > value finds the mid-1 position in the array from the low position, which is to the left of the middle value
                return this.binarySearchRecursive(array, value, low, mid - 1);
            } else {
                // If the target value is found, return the index
                returnmid; }}return null;
    }
Copy the code

Next, let’s use an example to test if the above code executes correctly:

const array = [7.8.1.2.3.5.12.13.16.19];
const searchArithmetic = new SearchArithmetic(array, 7);
const mid = searchArithmetic.binarySearchR();
console.log(mid);
Copy the code

Dynamic programming

Dynamic programming is an optimization technique for solving complex problems by breaking them down into smaller sub-problems, as opposed to divide-and-conquer, which is to break problems into independent sub-problems and then compose their answers. Dynamic programming decomposes the problem into interdependent subproblems.

Algorithm thought

The way we used recursion to solve the Fibonacci problem was dynamic programming. Characteristics of dynamic programming:

  • Overlapping subproblems: Subproblems occur repeatedly
  • Optimal substructure: The optimal solution of a problem contains the optimal solution of its subproblems
  • No aftereffect: Once the state of a stage is determined, the evolution of the subsequent process is no longer influenced by previous states and decisions.

The steps to solve the dynamic programming problem:

  • Decompose the original problem into sub-problems and determine what are the sub-problems
  • Determine the state transition equation, that is, determine the relationship between the previous state and the next state
  • Determining boundary conditions

Instance to explain

Next, let’s take a closer look at dynamic programming with some examples.

Minimum coin change problem

The problem is: given a total amount of change and a group of several denominations of coins, using the given denomination of coins to make change, how to need the least number of coins change.

As shown in the figure below, we use an example to explain the implementation ideas and implementation process.



Above we have drawn a sketch detailing what each step does, and now we can translate the above ideas into code implementation ideas.

Since we want to break the big problem into smaller problems, we will implement it recursively.

  • Declare a function (minCoinChange) that takes two parameters: coin denominationcoinsIt is of type array and the total amount of changeamountThe type is a number
  • Declares a two-dimensional arraycacheIt is used to store the combinations that have been found to prevent repeated calculation of the amount of the combinations that have been calculated once during recursive calculation, thus improving the time complexity of the algorithm. This technique is calledMemorization technique.
  • The function declares a recursive function (makeChange) inside, which accepts a change amount as a parameteramount, is used to divide big problems into small problems, and finally get the answer to the total problem. The internal implementation idea of the function is as follows.
    • First, we need to determine the termination condition for recursion, namelyamount == falsewhen
    • Second, judge the presentamountWhether the combination has been calculated. namelycache[amount]fortrueIf true, the combination stored in the cache is returned.
    • Declare the next three variables we need: minimum combinationmin, the minimum combination calculated by the recurrence of the previous layernewMin, the amount that needs to be recursed againnewAmount
    • Then, iteratecoinsArray, recursively dividing big questions into smaller ones to get the final answer.
      • Gets the value of the current traversal, that iscoin = coins[i]
      • withamount - coinisnewAmountThe value of the
      • If you calculate itnewAmountValues greater than or equal to 0 recurse, that is, add to the recursive stack
      • After the recursive execution is completed, we take out the data in the recursive stack in turn to judge whether the value meets the splicing condition. If so, we take out the data stored in the current recursive stackcoinThe value of andnewMinPerform splicing and assign the result to Min
    • At the end of traversal, assign min to cache[amounr], that is, put the found combination into cache, and return its result, which is the return value of the current stack, that isnewMinThe value of the.
  • The recursive function completes and the final answer is found. Return it.

The above idea is a bit convoluted, so let’s draw a picture to understand the above idea, as follows:

The implementation code

Next, let’s look at the code implementation.

/ * * * *@param Coin denomination *@param Change amount */
    minCoinChange(coins: number[].amount: number) :number[] {
        // Mnemonization technique, the purpose is to be smaller and do not count the value twice
        const cache: number[] [] = [];const makeChange = (amount: number) = > {
            // Return an empty array if amount is false
            if(! amount) {return [];
            }
            // Return the result if it is already cached
            if (cache[amount]) {
                return cache[amount];
            }
            let min: number[] = [],
                newMin: number[] = [],
                newAmount: number;
            for (let i = 0; i < coins.length; i++) {
                const coin = coins[i];
                newAmount = amount - coin;
                if (newAmount >= 0) {
                    // Add newAmount to the recursive stack
                    newMin = makeChange(newAmount);
                }
                // If the condition is met, the current coin will be executed
                if (newAmount >= 0 && (newMin.length < min.length - 1| |! min.length) && (newMin.length || ! newAmount)) {// Take the coin value stored in the current recursive stack, concatenate it with the newMin array, and assign the result to minmin = [coin].concat(newMin); }}// Assign min to cache[amount] and return the result, which is the return value of the current stack (newMin)
            return (cache[amount] = min);
        };
        return makeChange(amount);
    }
Copy the code

Write test code

Let’s put the example above into code to see if our function is executing correctly.

import { DesignSkills } from "./lib/DesignSkills.ts";
const designSkills = new DesignSkills();
const result = designSkills.minCoinChange([1, 5, 10, 25], 8);
console.log(result);
Copy the code

Knapsack problem

The backpack problem is a combinatorial optimization problem, which is described as follows: given a backpack of fixed size that can carry weight W and a group of valuable and heavy items, find an optimal solution so that the total weight of items in the backpack does not exceed W and the total value is the maximum.

Next, let’s use an example to draw some sketches to explain the backpack problem.



As shown in the picture above, there are 3 items, their weight and value as shown in the picture, assuming the backpack capacity is only 5. The best solution is to put item 1 and item 2 in the bag so that the total weight is 5 and the total value is 7.

So the above results are calculated by the human brain, and we will use dynamic programming to solve the problem, using dynamic programming to solve the problem requires two steps:

  • Structure matrix
  • You derive the combination from the matrix

Let’s take a look at the construction steps of the matrix first. The data we need are weights of items, values of items, capacity of backpack, and number of items n

  1. Declares and initializes the kS two-dimensional table, the matrix
  2. Iterate over all items (n), i.ei <= n

    Traverses the backpack capacity and starts filling the backpack, i.ew <= capacity

    The filling rule is as follows:

    (1). Wheni == 0 || w == 0When,kS[i][w] = 0

    (2). When the element of the i-1 position of the item weights is less than or equal to w, that isweights[i-1] <= wDeclare two auxiliary variables A and b,a = values[i - 1] + kS[i-1][w-weights[i-1]].b = kS[i-1][w]Let’s take the maximum value of a and bKS[i][w]The value of thatkS[i][w] = max(a,b).

    (3). When the weight exceeds the weight that the backpack can carry, thenkS[i][w] = kS[i-1][w]

For example: values = [3, 4, 5]; weights = [2, 3, 4]; capacity = 5, n = 3

  • I = 0,w = 0,kS[0][0] = 0
  • When I = 0 and w = 1,kS[0][1] = 0
  • When I = 0 and w = 2,kS[0][2] = 0
  • When I is 0 and w is 3,kS[0][3] = 0
  • When I is 0 and w is 4,kS[0][4] = 0
  • When I is 0 and w is 5,kS[0][5] = 0

  • When I = 1 and w = 0,kS[1][0] = 0
  • When I = 1 and w = 1,weights[1-1] = 2; 2 > w, kS[i][j] = kS[i-1][w] = kS[0][1] = 0
  • When I = 1 and w = 2,weights[i-1] = 2, 2 = w, a = values[1-1] + kS[1-1][2 - weights[1-1]] = values[0] + kS[0][2 - 2] = 3 + 0 = 3; b = kS[1-1][w] = 0; KS [I][w] = Max (3,0) = 3
  • When I = 1 and w = 3,weights[i-1] = 2, 2 < w, a = values[1-1] + kS[1-1][3 - weights[1-1]] = values[0] + kS[0][3-2] = 3 + 0 = 3; b = kS[1-1][w] = 0; KS [I][w] = Max (3,0) = 3
  • When I = 1 and w = 4,weightd[i-1] = 2, 2 = 2, a = values[1-1] + kS[1-1][4 - weights[1-1]] = 3 + 0 = 3; b = kS[1-1][w] = 0; KS [I][w] = Max (3,0) = 3
  • When I = 1 and w = 5,weights[i-1] = 2, 2 < 2, a = values[1-1] + kS[i-1][5 - weights[1-1]] = 3 + 0 = 3; b = kS[1-1][w] = 0; KS [I][w] = Max (3,0) = 3



Continue filling according to the above ideas. The final filled matrix is shown in the figure below. The last value of the table is the maximum total value we need.



Then we can deduce the composition scheme of items according to the matrix, and the steps are as follows.

We’ll start with the last cell of the matrix and work our way forward according to the following rules:

  • Item count and knapsack capacity must be greater than 0. If so, execute a while loop
  • When the matrix[i][k]The element of position is not equal to[i-1][k]The element of the position, then it is pulled out
  • After taking it out, change the values of I and w, i.ei--; k -= kS[i][k]

For example: the data we need and the data we need to construct the matrix are more than a constructed knapsack maximum matrix kS

  • When I = 3 and k = 5,kS[3][5] = 7, kS[2][5] = 7The two are equal, so look up, i.ei--.
  • When I = 2 and k = 5,kS[2][5] = 7, kS[1][5] = 4If the two are not equal, the combination is formed and the combination is taken out, namely:[weights[i-1], values[i-1]] = [3, 4]And theni--; k = k - kS[i][k] = 5 - kS[1][5] = 5 - 3 = 2
  • In this case, I = 1, k = 2,kS[1][2] = 3, kS[0][2] = 0If the two are not equal, the combination is formed and the combination is taken out, namely:[weights[i-1], values[i-1]] = [2, 3]And theni--; k = k - kS[i][k] = 2 - 0 = 2Now,i = 0Condition not met, all combinations found exit loop.

Finally, the combinations found are: [3,4] and [2,3], namely, item 1 and item 2. It’s consistent with what we did in our head at the beginning.

The implementation code

Now let’s translate this idea into code.

/** * The backpack problem is: given a backpack of a fixed size that can carry weight W and a group of valuable and heavy items, find an optimal solution so that the total weight of the items in the backpack does not exceed w and the total value is the maximum *@param Capacity Capacity of the backpack *@param Weights Weight of an item *@param Values Item value *@param N Item quantity */
    knapSack(capacity: number.weights: number[].values: number[].n: number) :number {
        // Declare and initialize matrices that need to find solutions
        const kS: number[] [] = [];for (let i = 0; i <= n; i++) {
            kS[i] = [];
        }
        for (let i = 0; i <= n; i++) {
            for (let w = 0; w <= capacity; w++) {
                if (i === 0 || w === 0) {
                    // Ignore the first column and row of the matrix and process only those columns and rows whose index is not 0
                    kS[i][w] = 0;
                } else if (weights[i - 1] <= w) {
                    // Item I must weigh less than the constraint
                    const a = values[i - 1] + kS[i - 1][w - weights[i - 1]].const b = kS[i - 1][w];
                    console.log(`i = ${i} :( a = ${a} , b = ${b}) `);
                    // When finding items that can form a solution, choose the one with the greatest value
                    kS[i][w] = a > b ? a : b;
                } else {
                    // The total weight exceeds the weight the backpack can carry, ignoring the value before it was used
                    kS[i][w] = kS[i - 1][w];
                }
            }
        }
        DesignSkills.findValues(n, capacity, kS, weights, values);
        return kS[n][capacity];
    }
    /** * Find backpack items to form scheme combinations *@param N Quantity of items *@param Capacity Capacity of the backpack *@param KS knapsack maximum value matrix *@param Weights Weight of an item *@param Values Item value *@private* /
    private static findValues(n: number.capacity: number.kS: number[] [].weights: number[].values: number[]) :void {
        let i = n;
        let k = capacity;
        console.log("Objects of solution");
        // Execute the loop when both item count and backpack capacity are greater than 0
        while (i > 0 && k > 0) {
            if(kS[i][k] ! == kS[i -1][k]) {
                // kS[I][k] is not equal to kS[I -1][k]
                console.log(` items${i}Can be part of the solution w,v:${weights[i - 1]}.${values[i - 1]}; `);
                // reassign I and k
                i--;
                k -= kS[i][k];
            } else {
                / / to find upi--; }}}Copy the code

Write test code

We put the start ownership problem into the code to test whether the function we write can execute correctly.

import { DesignSkills } from "./lib/DesignSkills.ts";
const designSkills = new DesignSkills();
const values = [3.4.5],
    weights = [2.3.4],
    capacity = 5,
    n = values.length;
console.log("The maximum value of all constituent options is", designSkills.knapSack(capacity, weights, values, n));
Copy the code

Longest common subsequence

The longest common subsequence is to find the oldest sequence of two sequences of strings. The oldest sequence is a sequence of strings that occurs in the same order but does not require contiguity. Such as:

A string of 1 a c b a e d
String 2 a b c a d f

In the table above, two strings are described, and their longest common subsequence is: AcAD is the same as knapsack problem, here we also need to work out the length of the longest common subsequence by constructing a matrix. Then the common subsequence is derived from the obtained matrix. So, let’s first look at the construction idea of this matrix:

  1. Two arguments are required: the string 1wordX, string 2wordY
  2. Declare two auxiliary variablesm,nTo receive the length of two strings.
  3. The statement matrixl, and initialize it to 0
  4. Iterate over the two strings and fill the matrix according to the following rules:

    (1). Wheni==0 || j == 0whenl[i][j] = 0

    (2). WhenwordX[i - 1] == wordY[j - 1]whenl[i][j] = l[i - 1][j - 1] + 1

    (3). Otherwise, declare two auxiliary variablesa,b.a = [i - 1][j]; b = [i][j - 1], take the maximum value of bothl[i][j]The value of the output is 1, 2, 3l[i][j] = max(a, b)

Next, we populate an instance with the procedure above:



As shown in the figure above, when the same values in the solved matrix are diagonally aligned, we add characters to the answer, so we need to rebuild the matrixsolution, its construction rules are as follows:

  1. wheni == 0 || j == 0whenS[i][j] = 0
  2. whenwordX[i - 1] == wordY[j - 1]whenS[i][j] = "diagonal"
  3. Otherwise,S[i][j] = l[i - 1][j]? "top" : "left"
S 0 1 2 3 4 5 6 ( j )
0 0 0 0 0 0 0 0 0
1 0 diagonal left left diagonal left left
2 0 top top diagonal left left left
3 0 top diagonal top top top top
4 0 diagonal top top diagonal left left
5 0 top top top top top top
6 0 top top top top diagonal left
( i )

Then, we can deduce the combination according to the matrix, we use m, n, the rules are as follows:

  1. ifsolution[m][n] == "diagonal"I take it out and splice it, and thena--; b--
  2. ifsolution[m][n] == "left",b--
  3. ifsolution[m][n] == "top",a--

Such as:

  • whenm = 6, its value is left, then b–
  • At this point,m = 6,n = 5, and the value is diagonal, then the value is extracted and spliced, namely:answer = wordX[a-1] + answer = "d". thena--, b--
  • At this point,m = 5, n=4, its value is top, thena--
  • At this point,m = 4, n = 4Is diagonal, and is taken out, i.e.answer = wordX[a-1] + answer = "ad"And thena--, b--
  • At this point,m = 3, n = 3, its value is top, thena--
  • At this point,m = 2, n = 3Is diagonal, and is taken out, i.e.answer = wordX[a-1] + answer = "cad"And thena--, b--
  • At this timem = 1, n = 2, its value is left, thenb--
  • At this point,m = 1, n = 1Is diagonal, and is taken out, i.e.answer = wordX[a-1] + answer = "acad"And thena--, b--;
  • At this point,m = 0, n = 0, the combination derivation is completed,Longest common subsequence: ACAD

The implementation code

Next, let’s translate this idea into code.

/** * the longest common subsequence *@param WordX The string is 1 *@param WordY string 2 */
    lcs(wordX: string.wordY: string) :number {
        // Get the length of two subsequences
        const m = wordX.length;
        const n = wordY.length;
        // Declare and initialize a two-dimensional array to hold a matrix
        const l: number[] [] = [];for (let i = 0; i <= m; i++) {
            l[i] = [];
            for (let j = 0; j <= n; j++) {
                l[i][j] = 0; }}for (let i = 0; i <= m; i++) {
            for (let j = 0; j <= n; j++) {
                if (i === 0 || j === 0) {
                    // if I is 0 or j is 0, the cell is filled with 0
                    l[i][j] = 0;
                } else if (wordX[i - 1] === wordY[j - 1]) {
                    // The value of i-1 of string 1 is equal to the value of j-1 of string 2
                    l[i][j] = l[i - 1][j - 1] + 1;
                } else {
                    // Otherwise, take the values of a and B and select a larger value to fill
                    const a = l[i - 1][j];
                    const b = l[i][j - 1]; l[i][j] = a > b ? a : b; }}}// The last cell is the length of the longest common subsequence
        return l[m][n];
    }
    /** * longest common subsequence solution *@param wordX
     * @param wordY* /
    lcsSolution(wordX: string.wordY: string) :string {
        // Get the length of two subsequences
        const m = wordX.length;
        const n = wordY.length;
        // Declare and initialize a two-dimensional array to hold a matrix
        const l: number[] [] = [];// Store a matrix for deriving combinations
        const solution: string[] [] = [];for (let i = 0; i <= m; i++) {
            l[i] = [];
            solution[i] = [];
            for (let j = 0; j <= n; j++) {
                l[i][j] = 0;
                solution[i][j] = "0"; }}for (let i = 0; i <= m; i++) {
            for (let j = 0; j <= n; j++) {
                if (i === 0 || j === 0) {
                    l[i][j] = 0;
                } else if (wordX[i - 1] === wordY[j - 1]) {
                    l[i][j] = l[i - 1][j - 1] + 1;
                    // Fill in the diagonal if equal
                    solution[i][j] = "diagonal";
                } else {
                    const a = l[i - 1][j];
                    const b = l[i][j - 1];
                    l[i][j] = a > b ? a : b;
                    // Fill top if it is equal, otherwise fill left
                    solution[i][j] = l[i][j] == l[i - 1][j] ? "top" : "left"; }}}// select * from the list
        return DesignSkills.getSolution(solution, wordX, m, n);
    }
    /** * Derive its combination scheme from the longest common subsequence matrix *@param Solution Longest common subsequence matrix *@param WordX The string is 1 *@param The X-axis of the m-matrix points to star@param The Y-axis of the n-matrix points to star@private* /
    private static getSolution(solution: string[] [].wordX: string.m: number.n: number) :string {
        let a = m;
        let b = n;
        let x = solution[a][b];
        let answer = "";
        while(x ! = ="0") {
            if (solution[a][b] === "diagonal") {
                // If it equals, take it out
                answer = wordX[a - 1] + answer;
                a--;
                b--;
            } else if (solution[a][b] === "left") {
                b--;
            } else if (solution[a][b] === "top") {
                a--;
            }
            // Reassign to continue the next loop
            x = solution[a][b];
        }
        // return the combined scheme
        return answer;
    }
Copy the code

Write test code

Let’s put the example above into the code to see if the above function executes correctly.

import { DesignSkills } from "./lib/DesignSkills.ts";
const designSkills = new DesignSkills();
const solution = designSkills.lcsSolution("acbaed"."abcadf");
console.log(solution);
Copy the code

Matrix chain multiplication

Given a sequence of n matrices :(A1,A2,A3,A4… ,An), calculate their product: A1A2A3A4… An, which minimizes multiplication. We know that matrix multiplication satisfies the associative law of multiplication, and that’s why we have the problem of matrix chain multiplication. The two matrices have the smallest multiplication times, and their multiplication times are calculated as follows: the size of the first matrix * the number of columns of the second matrix, that is, A(Mn) * B(NP) = MNP.

Problem analysis

Let’s analyze this problem with an example, as follows:

// Describe four matrices:
/ / A (10100).
/ / B (100, 5)
/ / C (5, 50)
/ / D (50, 1)
const p = [10.100.5.50.1]
Copy the code

Above, we describe four matrices whose optimal number of computations is1750, their optimal multiplication scheme is:(A * ( B * ( C * D ) ) )

So how are these numbers calculated? This involves the related knowledge of the line generation, I was also a face meng force at the beginning, after a search for information, and finally mastered the calculation rules.

Here briefly: if you want to know the calculation of matrix chain multiplication times, we must first know how two matrix multiplication, want to know between two matrix multiplication, we have to know how to multiply vectors, want to know how to multiply vectors, we have to know what is a vector, when we put all of these to learn later, found that this is the introductory line generation of knowledge.

Mathematics is so interesting, you can never directly solve a very complex problem, to solve this complex problem, you have to start from the most basic knowledge, one ring, one ring, after the knowledge system is satisfied, you can reasonably use these knowledge points to solve the complex problem at the beginning.

The correlation between matrices and vectors is more complex and not the focus of this article, but interested developers can read my other article:TypeScript implements vectors and matrices

As shown in the figure below, the multiplication times of matrix chain multiplication are analyzed.





The implementation code

Once we know the mathematical method of matrix chain multiplication, we can implement it with code as follows:

// Matrix chain multiplication
    matrixChainOrder(p: number[]) :number {
        // The length of the matrix
        const n = p.length;
        // Auxiliary matrix: m stores the optimal times
        const m: number[] [] = [];const s: number[] [] = [];// Complete fill matrix s
        for (let i = 0; i <= n; i++) {
            s[i] = [];
            for (let j = 0; j <= n; j++) {
                s[i][j] = 0; }}// Fill the matrix m diagonally
        for (let i = 1; i <= n; i++) {
            m[i] = [];
            m[i][i] = 0;
        }
        // Update the matrices m and s
        for (let l = 2; l < n; l++) {
            for (let i = 1; i <= n - l + 1; i++) {
                // Calculate the value of the position to fill
                const j = i + l - 1;
                // Assume that the value at this position is maximum
                m[i][j] = Number.MAX_SAFE_INTEGER;
                // console.table(m);
                for (let k = 0; k <= j - 1; k++) {
                    // The number of times the matrix is multiplied
                    const q = m[i][k] + m[k + 1][j] + p[i - 1] * p[k] * p[j];
                    // If the calculated degree is less than the assumed maximum value, update the elements of the M-matrix and s-matrix
                    if (q < m[i][j]) {
                        // the value at m[I][j] is the calculated numberm[i][j] = q; s[i][j] = k; }}}}// Prints the matrix multiplication combination order
        this.printOptimalParenthesis(s, 1, n - 1);
        // The first row of the m matrix at position I-1 is the minimum number of times we want to multiply the matrix chain
        return m[1][n - 1];
    }
    // Matrix chain multiplication solution
    printOptimalParenthesis(s: number[] [].i: number.j: number) :void {
        if (i === j) {
            console.log("A[" + i + "]");
        } else {
            console.log("(");
            this.printOptimalParenthesis(s, i, s[i][j]);
            this.printOptimalParenthesis(s, s[i][j] + 1, j);
            console.log(")"); }}Copy the code
Write test code

Let’s take the example in the figure above and put it into the code to see if the function we implemented is executing correctly.

const p = [10.100.5.50.1];
console.log("The optimal combination of matrix chain multiplication:");
const frequency = designSkills.matrixChainOrder(p);
console.log("Minimum number of matrix chains multiplied:", frequency);
Copy the code

The code address

For the code used in this article, go to the GitHub repository: DesignSkills.ts & DesignSkillsTest

Write in the last

  • If there are any errors in this article, please correct them in the comments section. If this article helped you, please like it and follow 😊
  • This article was first published in nuggets. Reprint is prohibited without permission 💌