Advanced algorithms

Dynamic programming

Dynamic programming is considered to be the opposite technique to recursion, which decompresses the problem from the top and then solves smaller problems

Recursion is inherently inefficient to perform, and many languages do not include recursion as a language feature for high-level programming.

Fibonacci series

0, 1, 1, 2,3,5, 8, 13….

function Fib(n) {
        var i = 0
        if (n < 2) {
            return n
        } else {
            return Fib(n-1) + Fib(n-2)
        }
    }
Copy the code

 function iterFib(n) {
        var last = 1
        var nextLast = 1
        var result = 1
        for (var i = 2; i < n; n++) {
            result = last + nextLast
            nextLast = last
            last = result
        }
        return result
    }
Copy the code

Look for the longest common substring

The public eldest son of Reaven Havoc is AV

Violent disassemble: Now given two strings A,B we will start A with the first character of B corresponding to find their firstborn string, if not found match the second character

Dynamic programming: Uses a two-dimensional array to store the result of a character comparison between two strings at the same position. When initialized, each element of the array is set to 0, and each time two arrays find a match, the elements in the corresponding row and column of the array are increments by one.

It records how many matches were found, and when the algorithm is finished, this variable is combined with an index to retrieve the longest common substring

function lcs(word1, word2) { var max = 0 var index = 0 var lcsarr = new Array(word1.length + 1) for (var i = 0; i <= word1.length + 1; i++) { lcsarr[i] = new Array(word2.length + 1) for (var j = 0; j <= word2.length + 1; ++j) { lcsarr[i][j] = 0 } } for (var i = 0; i <= word1.length + 1; i++) { for (var j = 0; j <= word2.length + 1; ++j) { if (i == 0 || j == 0) { lcsarr[i][j] = 0 } else { if (word1[i - 1] == word2[i - 1]) { lcsarr[i][j] = lcsarr[i - 1][j - 1] + 1 } else { lcsarr[i][j] = 0 } } if (max < lcsarr[i][j]) { max = lcsarr[i][j] index = i } } } var str = '' if  (max == 0) { return '' } else { for (var i = index - max; i <= max; i++) { str += word2[i] } return str } }Copy the code

Knapsack problem

The five items in the safe are 3,4,7,8,9 and their values are 4,5,10,11,13, while the backpack space is 16. So the proper thing to do is to take the third and fifth.

Function Max (a, b) {return (a > b)? a : b } function knapsack(capacity, size, value, n) { if (n == 0 || capacity == 0) { return 0 } if (size[n - 1] > capacity) { return knapsack(capacity, size, value, n - 1) } else { return max(value[n - 1] + knapsack(capacity - size[n - 1], size, value, n - 1), knapsack(capacity, size, value, n - 1)) } }Copy the code

Dynamic programming

function DKnapsack(capacity, size, value, n) {
        var K = []
        for (var i = 0; i <= capacity; i++) {
            K[i] = []
        }
        for (var i = 0; i <= n; i++) {
            for (var w = 0; w <= capacity; w++) {
                if (i == 0 || w == 0) {
                    K[i][w] = 0
                } else if (size[i-1] <= w) {
                    K[i][w] = max(value[i-1] + K[i-1][w-size[i-1]], K[i-1][w])
                } else {
                    K[i][w] = K[i-1][w]
                }
                console.log(K[i][w] + ' ')
            }
        }
        return K[n][capacity]
    }
Copy the code

Greedy algorithm

You go to the store and you get 63 cents change, and the clerk, according to the greedy algorithm, will give you 2 * 25 + 1 * 10 + 3 * 1, which is the smallest number of coins without a 50 cent coin.