Dynamic programming

The core, as I understand it, is a greedy strategy, where the outcome depends on the previous operation or its substructure and the main idea is to find the optimal substructure

The Fibonacci series

Let’s start with a simple Fibonacci sequence 1, 1, 2, 3, 5, 8…… For example, to find the NTH number, you need to know n minus one and n minus two, so n starts at zero

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

However, recursive operations are often very wasteful of memory, and stack overflow may occur, so we can use a non-recursive way to achieve the Fibonacci sequence

    function Fib(n){
        if(n<2) return 1
        var preone=1
        var pretow=1
        var res=0
        for(let i=2; i<=n; i++){ res=preone+pretwo pretwo=preone preone=res }return res
    }
Copy the code

Frog jumping problem

A frog can jump up one step at a time, or two steps at a time. Find out how many ways the frog can jump up n steps

Func(n-1)+ Func(n-2) = Func(n-1)+ Func(n-2)

Isn’t that the Fibonacci sequence? (1,1,2,3)

    function Fib(n){
    // there is only one hop for n==0 and only one hop for n==1
        if(n<2) return 1
        let preone = 1
        let pretwo = 1
        let res=0
        for(let i=2; i<=n; i++){ res=preone+pretwo pretwo = preone preone = res }return res
    }
Copy the code

Maximum profit of stock

If store the price of some stock according to time sequence successively in array, excuse me the biggest profit that business this stock may obtain is how many example

Input:,1,5,3,6,4 [7]

Output: 5

The stock maximum return problem is a classic dynamic programming problem. We use dp=[] to store the maximum return that can be obtained in the current and previous days. Dp needs to be initialized, because DP [I] depends on D [i-1] DP [0]=0

    function maxProfit(arr){
        if(arr.length<2) return 0
        var dp=[]
        dp[0] =0
        mincost=arr[0]// Record the current minimum cost (i.e. purchase price)
        for(let i=1; i<arr.length; i++){ dp[i]=Math.max(dp[i-1],arr[i]-mincost)
            mincost = Math.min(mincost,arr[i])
        }
        return dp[arr.length-1]}Copy the code

Maximum gift value

A gift is placed on each square of an M * N board, and each gift has a value (value greater than 0). You can start at the top left of the board and move one space to the right or down until you reach the bottom right of the board. Given the value of a chess board and the gifts on it, calculate the maximum value of gifts you can get.

Dp =[] dp[0][0]=grid[0][0]

    function maxGiftValue(grid){
        let m=grid.length/ / the number of rows
        let n=grid[0].length/ / the number of columns
        var dp=[]
        for(let i=0; i<m; i++){ dp.push([])for(let j=0; j<n; j++){if(i==0&&j==0) dp[i][j]=grid[i][j]
                else if(i==0&&j! =0) dp[i][j]=dp[i][j-1]+grid[i][j]
                else if(i! =0&&j==0) dp[i][j]=dp[i-1][j]+grid[i][j]
                else dp[i][j]=Math.max(dp[i][j-1],dp[i-1][j])+grid[i][j]
            }
        }
        return dp[m-1][n-1]}Copy the code

The longest substring without repeating characters

Please find the longest substring that does not contain repeated strings from the string, calculate the length of the longest string using a sliding window, double pointer control sliding window size

    function lengthOfLongestSubstring(str){
        let map = new Map(a)let left = 0
        let right = 0
        let res = 0
        while(right<str.length){
            let cur = str[right]
            if(map.get(cur)>=0){
                left = Math.max(left,map.get(cur)+1)
            }
            map.set(cur,right)
            res = Math.max(res,right-left+1)
            right++
        }
        return res
        
    }
Copy the code