## 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 developers
`binarySearchR`

Realization idea:- Calls the sort method to sort the sorted array
- Declare two auxiliary variables
`lwo`

and`high`

And the values are respectively`0`

and`array.length - 1`

, used to define the split point from where in the array to where to perform divide-and-conquer. - call
`binarySearchRecursive`

Function that returns the result.

- Now, let’s look at the divide-and-conquer function
`binarySearchRecursive`

Realization idea:- It takes four arguments: a partitioned array
`array`

The target value of,`value`

, array start point decomposition point`low`

, array end decomposition point`high`

- If low <= high, compute the intermediate index
`mid`

, extract the median value`element`

. Perform the following judgments:- if
`element < value`

, represents that the target value is to the right of the median value, then from`mid + 1`

The position starts to decompose the array to`high`

The location performs divide-and-conquer - if
`element > value`

, represents that the target value is to the left of the median value, then from`low`

The position starts to decompose the array to`mid - 1`

The location performs divide-and-conquer - Otherwise it is
`element ===value`

, target value found, return mid.

- if

- It takes four arguments: a partitioned array
- Otherwise,
`low > high`

, the target value is not in the array, returns`null`

.

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 denomination
`coins`

It is of type array and the total amount of change`amount`

The type is a number - Declares a two-dimensional array
`cache`

It 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 called**Memorization technique**. - The function declares a recursive function (makeChange) inside, which accepts a change amount as a parameter
`amount`

, 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, namely
`amount == false`

when - Second, judge the present
`amount`

Whether the combination has been calculated. namely`cache[amount]`

for`true`

If true, the combination stored in the cache is returned. - Declare the next three variables we need: minimum combination
`min`

, the minimum combination calculated by the recurrence of the previous layer`newMin`

, the amount that needs to be recursed again`newAmount`

- Then, iterate
`coins`

Array, recursively dividing big questions into smaller ones to get the final answer.- Gets the value of the current traversal, that is
`coin = coins[i]`

- with
`amount - coin`

is`newAmount`

The value of the - If you calculate it
`newAmount`

Values 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 stack
`coin`

The value of and`newMin`

Perform splicing and assign the result to Min

- Gets the value of the current traversal, that is
- 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 is
`newMin`

The value of the.

- First, we need to determine the termination condition for recursion, namely
- 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

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

Traverses the backpack capacity and starts filling the backpack, i.e`w <= capacity`

The filling rule is as follows:

(1). When`i == 0 || w == 0`

When,`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 is`weights[i-1] <= w`

Declare 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 b`KS[i][w]`

The value of that`kS[i][w] = max(a,b)`

.

(3). When the weight exceeds the weight that the backpack can carry, then`kS[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.e
`i--; 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] = 7`

The two are equal, so look up, i.e`i--`

. - When I = 2 and k = 5,
`kS[2][5] = 7, kS[1][5] = 4`

If 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 then`i--; 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] = 0`

If 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 then`i--; k = k - kS[i][k] = 2 - 0 = 2`

Now,`i = 0`

Condition 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:

- Two arguments are required: the string 1
`wordX`

, string 2`wordY`

- Declare two auxiliary variables
`m`

,`n`

To receive the length of two strings. - The statement matrix
`l`

, and initialize it to 0 - Iterate over the two strings and fill the matrix according to the following rules:

(1). When`i==0 || j == 0`

when`l[i][j] = 0`

(2). When`wordX[i - 1] == wordY[j - 1]`

when`l[i][j] = l[i - 1][j - 1] + 1`

(3). Otherwise, declare two auxiliary variables`a,b`

.`a = [i - 1][j]; b = [i][j - 1]`

, take the maximum value of both`l[i][j]`

The value of the output is 1, 2, 3`l[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 matrix`solution`

, its construction rules are as follows:

- when
`i == 0 || j == 0`

when`S[i][j] = 0`

- when
`wordX[i - 1] == wordY[j - 1]`

when`S[i][j] = "diagonal"`

- 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:

- if
`solution[m][n] == "diagonal"`

I take it out and splice it, and then`a--; b--`

- if
`solution[m][n] == "left"`

,`b--`

- if
`solution[m][n] == "top"`

,`a--`

Such as:

- when
`m = 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"`

. then`a--, b--`

- At this point,
`m = 5, n=4`

, its value is top, then`a--`

- At this point,
`m = 4, n = 4`

Is diagonal, and is taken out, i.e.`answer = wordX[a-1] + answer = "ad"`

And then`a--, b--`

- At this point,
`m = 3, n = 3`

, its value is top, then`a--`

- At this point,
`m = 2, n = 3`

Is diagonal, and is taken out, i.e.`answer = wordX[a-1] + answer = "cad"`

And then`a--, b--`

- At this time
`m = 1, n = 2`

, its value is left, then`b--`

- At this point,
`m = 1, n = 1`

Is diagonal, and is taken out, i.e.`answer = wordX[a-1] + answer = "acad"`

And then`a--, 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 is**1750**, 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 💌