Dynamic programming problem (1) — Fibonacci sequence

Topic recently has been writing for several algorithm, found a very cow force algorithm, dynamic programming, although some of their thinking and dynamic planning, but didn’t know the principle and some generality, in the next few days, with some chestnuts and open the mystery of the dynamic programming that bit by bit face cream, I also learn now sell now, If there is something wrong, please leave a message and correct it.

Dynamic programming is sometimes referred to as the inverse technique of recursion. Recursion is breaking the problem down from the top, solving the whole problem by solving all the smaller problems. Dynamic programming, on the other hand, solves problems from the bottom up, solves all the small problems, and then merges them into a holistic solution that solves the big problem. Recursion is concise but inefficient, but it’s not bad. Essentially, imperative and object-oriented languages don’t implement recursion well enough because they don’t make recursion a high-level programming feature.

Dynamic programming schemes typically use an array to create a table of solutions that are broken down into subproblems. ** When the algorithm completes, the final solution will be found in this table.

Today we’re going to start with our most familiar Fibonacci sequence.

0, 1, 1, 2, 3, 5, 8, 13, 21, 24, 55...Copy the code

You can see from the sequence that the value starting with the third number is the sum of the first two values.

The recursive method

function fib(n){ if(n < 2){ return n; }else{ return fib(n - 1) + fib(n - 2); } } console.log(fib(10)); / / 55Copy the code

Dynamic programming solution

function fibDyn(n){
    var temp = [];
    for(var i = 0; i <= n; i++){
        temp[i] = 0
    }
    if(n == 1 || n == 2){
        return 1;
    }else{
        temp[1] = 1;
        temp[2] = 2; 
        for(var i = 3; i < n; i++){
            temp[i] = temp[i - 1] + temp[i -2];
        }
        return temp[i - 1];
    }
}
fibDyn(10)  // 55Copy the code

From the program, we can see that an empty array of the same length as the incoming is initialized to store the result of each operation.

Test program run time

var start = new Date().getTime(); console.log(fib(10)) var stop = new Date().getTime(); Console. log(' recursive consumption '+ (stop-start) +' milliseconds ');Copy the code

start = new Date().getTime(); console.log(fibDyn(10)) stop = new Date().getTime(); Console. log(' dynamic planning consumption '+ (stop-start) +' milliseconds ');Copy the code

The results

55 Recursive cost -- 0 ms 55 Dynamic planning cost -- 0 msCopy the code

fib(20)

6765 Recursive cost -- 1 ms 6765 Dynamic planning cost -- 0 msCopy the code

fib(30)

832040 Recursive cost -- 17 ms 832040 Dynamic planning cost -- 0 msCopy the code

If we change the n in fib of n, we see that dynamic programming is much more efficient than recursive programming.

Optimization of dynamic programming algorithm for Fibonacci sequence

We see that the dynamic programming algorithm takes an empty array, and that’s why you might have thought of using an iterative scheme, instead of using an array, using a set of elements because dynamic programming algorithms usually need to store the intermediate result. Here is the optimized iteration.

function fibDyn(n){
    var prev = 1;
    var middle = 1;
    var result = 1;

    for(var i = 2; i < n; i++){
        result = prev + middle;
        prev = middle;
        middle = result;
    }
    return result;
}
fibDyn(10)  // 55Copy the code

At this point, we can see that without creating an array, the efficiency is the same, but the space complexity is smaller.

The Fibonacci sequence is used in many places, and I discovered it from a step problem, and I learned the solution to dynamic programming.

---

Did this article help you? Welcome to join the front End learning Group wechat group: