Detailed explanation of the use of JS dynamic programming

This time I will bring you a detailed explanation of the use of JS dynamic programming. What are the precautions when using JS dynamic programming? Here are practical cases, let’s take a look.

In fact, in our front-end development, there are not many advanced algorithms used. In most cases, if statements, for statements, swith statements, etc. can be solved . If it's a little more complicated, you might think of using recursion to solve it.

But it should be noted that recursion is simple to write, but in fact it is not very efficient in execution.

Let’s look at the dynamic programming algorithm again:

Dynamic programming solutions start at the bottom, solving all the small problems, and then combine them into a holistic solution to solve the entire big problem.

Example (Calculating Fibonacci Sequence)

The Fibonacci sequence refers to a sequence of numbers 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765 ,10946,17711,28657,46368.....

This sequence starts with item 3, and each item is equal to the sum of the previous two items.

For this sequence, you can use a recursive function to calculate the nth item value

// 斐波那契数列
function recurFib(n) {
    if(n ");
      return recurFib(n-1)+recurFib(n-2)
    }
}

It is indeed a very concise code. The commented code above is used to print out how many times the function needs to be executed when n =. However, a discerning person can see at a glance that the number of executions will increase as n increases. Very scary growth.

When n=5, the recursion tree has grown very big... It can be predicted that when n=10, or even n=100...

After understanding the difference in execution efficiency of recursive functions, let’s look at how dynamic programming is done

function dynFib(n) {
  let val = [];
  for(let i = 0; i <p style="text-align: left;">
The intermediate result is saved in the array val. If the Fibonacci number to be calculated is 1 or 2, then the if statement will return 1. Otherwise, the values ​​1 and 2 will be stored at positions 1 and 2 in the val array. </p><p style="text-align: left;">
The loop will traverse from 3 to the input parameters, and assign each element of the array to the sum of the first two elements. When the loop ends, the last element value of the array is the final calculated Fibonacci value. This value will also be used as the return value <a href="http://www.php.cn/code/6029.html" target="_blank"> of the </a> function. </p><p style="text-align: left;">
Next, you can write a simple test function to compare the running time of the two. </p><pre class="brush:php;toolbar:false">// 定义一个测试函数，将待测函数作为参数传入
function test(func,n){
  let start = new Date().getTime();//起始时间
  let res = func(n);//执行待测函数
  document.write('<br>'+'当n='+n+'的时候 '+res+'<br>');
  let end = new Date().getTime();//结束时间
  return (end - start)+"ms";//返回函数执行需要时间
}

Print function execution

let time = test(recurFib,40);
document.write(time);
let time2 = test(dynFib,40);
document.write(time2);

The results are as follows:

Finally, you may have realized that it is possible to calculate the Fibonacci sequence without using arrays when using an iterative approach.

The reason why arrays are needed is because dynamic programming algorithms usually need to save intermediate results.

The following is the iterative version of the Fibonacci function meaning

function iterFib(n) {
  let last = 1;
  let nextLast = 1;
  let result = 1;
  for (let i = 2; i <p style="text-align: left;">
Of course, the efficiency of this iterative version is the same as that of the array version. </p><p> I believe you have mastered the method after reading the case in this article. For more exciting information, please pay attention to other related articles on the php Chinese website! </p><p>Recommended reading:</p><p><a href="http://www.php.cn/js-tutorial-392657.html" target="_blank">How to use Angular4 input and output</a><br></p><p><a href="http://www.php.cn/js-tutorial-392661.html" target="_blank">How to operate user permissions in Vue2.0</a><br></p><p style="text-align: left;">
</p><!--content end-->

The above is the detailed content of Detailed explanation of the use of JS dynamic programming. For more information, please follow other related articles on the PHP Chinese website!