I. Title Description:

Leetcode-cn.com/problems/mi… You are given a 3 runway road of length N, which contains a total of N + 1 points, numbered 0 through N. A frog starts from lane 2 at point 0 and wants to jump to point N. There may be some bumps in the road, however.

You are given an array of obstacles of length n + 1, where obstacles[I] (range from 0 to 3) indicate that there is an obstacle in the path of obstacles[I] at point I. If [I] == 0, there is no obstacle at point I. There is no more than one obstacle in any of the three tracks at any one point.

For example, if he is lazy [2] == 1, then there is an obstacle in track 1 at point 2. The frog jumps from point I to point I + 1 and the runway stays the same as long as there are no obstacles on the same runway at point I + 1. In order to avoid obstacles, the frog can also side jump to another runway at the same point (the two lanes may not be adjacent), but only if there are no obstacles at that point.

For example, this frog can jump from runway 3 at point 3 to runway 1 at point 3. This frog starts from runway 2 at point 0 and wants to reach any runway at point n, please return to the minimum number of side jumps.

Note: neither runway at point 0 nor point N will be obstructed.

**** Example 1:

Input: lazy = [0,1,2,3,0] output: 2 explanation: the optimal scheme is shown by the arrow in the figure above. There are two side jumps in total (red arrows). Note that the frog can only jump over obstacles if it jumps on its side (as shown at point 2 above).Copy the code

Ii. Analysis of Ideas:

  • DFS + memorized search
  • The DFS function is defined as starting from the currLine runway at n points and taking several jumps to the finish line
  • F (currLine, n)
    • If there is an obstacle, f(n) = f(Nextline, n +1)+1
    • If f(n) = f(Nextline, n + 1)
  • Note that the n and n+1 points of nextline should not be obstructed

Iii. AC Code:

/ * * *@param {number[]} obstacles
 * @return {number}* /
var minSideJumps = function (obstacles) {

    const dp = new Array(4).fill(null).map(_= >new Array(obstacles.length))

    function dfs(currLine, n) {
        if (n === obstacles.length-1) {
            return 0
        }
        if(dp[currLine][n]! = =undefined) {return dp[currLine][n]
        }
        const blockLine = obstacles[n + 1]
        if(currLine ! == blockLine) {// The current runway is unblocked
            dp[currLine][n] = dfs(currLine, n + 1)
            return dp[currLine][n]
        } else {
            let min = Number.MAX_SAFE_INTEGER
            for (let i = 1; i <= 3; i++) { // Current runway is blocked
                if(i ! == blockLine && i! ==obstacles[n]) {// Cannot jump to a blocked runway at the next hop, or to a blocked runway at the current position
                    min = Math.min(min,dfs(i, n + 1) +1)
                }
            }
            dp[currLine][n] = min
            return min
        }

    }

    return dfs(2.0)};Copy the code

Iv. Summary:

  • A recursive function that captures a change in state, essentially a change in state, from the current state to the next state.