Shulou(Shulou.com)06/03 Report--

This article will explain in detail how to learn dynamic planning from the simplest Fibonacci series in the JavaScript version. the content of the article is of high quality, so the editor will share it for you as a reference. I hope you will have some understanding of the relevant knowledge after reading this article.

Preface

Fibonacci sequence is a classic problem. Although it is very simple, many practical optimization algorithms can be extended when optimizing and solving it.

Its concept is very simple. Let's take a look at the definition of him in LeetCode's real title:

Fibonacci numbers, usually represented by F (n), form a sequence called Fibonacci series. The sequence starts with 0 and 1, and each subsequent number is the sum of the first two numbers. That is:

F (0) = 0, F (1) = 1

F (N) = F (N-1) + F (N-2), where N > 1.

Given N, calculate F (N).

First, take a brief preview of what the Fibonacci series looks like:

1 、 1 、 2 、 3 、 5 、 8 、 13 、 21 、 34

Bronze Age-Recursive solution.

In this article, the following fib (n) represents the solution of n.

With the definition, our first intuition is that we can use "recursion" to solve this problem, and the idea is very simple, as long as we define the initial state, that is, fib (1) = 1 fib (2) = 1, then we assume that fib (3) only needs to find fib (2) + fib (1), and so on.

About in fib (50), ran on my notebook for 123.167 seconds, and then even more unimaginable. Due to a large number of recursive calls and repeated calculations, the speed of this algorithm is unacceptably slow.

Silver Age-memo solution

The solution of bronze is due to a large number of repeated calculations

For example, fib (3) calculates fib (2) + fib (1).

Fib (2) calculates fib (1) + fib (0).

This fib (1) is a completely repeated calculation, and it should not be called again recursively, but should be "memorized" after the first request to release it.

Liberate what you have already obtained in Map and take it directly next time instead of repeating the settlement.

It's a trick to use the iife function to form a closure and retain the private variable memo.

At this time, the calculation speed of fib (50) is up to 0.096 seconds, which is 1200 times faster than the bronze solution in the case of a small number of 50.

Some people who say that algorithms are useless hold the view that these differences will be erased with the progress of hardware, so I look forward to the day when the hardware will improve by 1000 times.

Golden Age-dynamic Planning

It seems that the above memo solution is perfect, but in fact it is not, although the memo solution optimizes the useless repetitive solutions and achieves a better speed.

However, for the first solution, the value that has not been memorized will still enter the recursive call logic.

For example, f (10000), then f (9999) and f (9998) must be called recursively. F (0), and in the process of recursion, these call stacks are constantly superimposed, when the depth of the function call, the stack has reached thousands of layers.

At this point, it will report a familiar error:

RangeError: Maximum call stack size exceeded at c:\ codes\ leetcode-javascript\ dynamic programming\ Fibonacci series-509.js:20:19 at c:\ codes\ leetcode-javascript\ dynamic planning\ Fibonacci series-509.js:32:14

Let's go back and think about it. Under the memo, our solution path is "top-down". What if we turn our thinking upside down and turn it into a "bottom-up" solution?

That is to say, for fib (10000), we learn from fib (1), fib (2), fib (3). Fib (10000)

The solution starts with the lowest value, and the value of each solution is saved in memory (which can be an array, and the subscript corresponds to the solution value of n). The following values are derived directly from the value in memory.

In this way, when we calculate to 10000, the value we want to ask for the solution will naturally be obtained, and we can directly get the value from memory [10000] and return it.

So this solution actually requires only a for loop and does not require any recursive logic.

In fact, this is a more classical solution of "dynamic programming", so is this algorithm powerful?

In the case of fib (10000), where neither of the above two solutions can be done, it took 0.114 seconds to get the result.

It took 0.827 seconds for fib (100000).

By the way, in JavaScript, this number is displayed as Infinity because it exceeds the maximum value. In fact, the solution is very simple, just use the data type of BigInt.

Summary

I hope the above content can be of some help to you and learn more knowledge. If you think the article is good, you can share it for more people to see.

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.