There is a 3 lane road of length n that consists of n + 1 points labeled from 0 to n. A frog starts at point 0 in the second lane and wants to jump to point n. However, there could be obstacles along the way.

You are given an array obstacles of length n + 1 where each obstacles[i] (ranging from 0 to 3) describes an obstacle on the lane obstacles[i] at point i. If obstacles[i] == 0, there are no obstacles at point i. There will be at most one obstacle in the 3 lanes at each point.


	For example, if obstacles[2] == 1, then there is an obstacle on lane 1 at point 2.


The frog can only travel from point i to point i + 1 on the same lane if there is not an obstacle on the lane at point i + 1. To avoid obstacles, the frog can also perform a side jump to jump to another lane (even if they are not adjacent) at the same point if there is no obstacle on the new lane.


	For example, the frog can jump from lane 3 at point 3 to lane 1 at point 3.


Return the minimum number of side jumps the frog needs to reach any lane at point n starting from lane 2 at point 0.

Note: There will be no obstacles on points 0 and n.

&nbsp;
Example 1:

Input: obstacles = [0,1,2,3,0]
Output: 2 
Explanation: The optimal solution is shown by the arrows above. There are 2 side jumps (red arrows).
Note that the frog can jump over obstacles only when making side jumps (as shown at point 2).


Example 2:

Input: obstacles = [0,1,1,3,3,0]
Output: 0
Explanation: There are no obstacles on lane 2. No side jumps are required.


Example 3:

Input: obstacles = [0,2,1,0,3,0]
Output: 2
Explanation: The optimal solution is shown by the arrows above. There are 2 side jumps.


&nbsp;
Constraints:


	obstacles.length == n + 1
	1 &lt;= n &lt;= 5 * 105
	0 &lt;= obstacles[i] &lt;= 3
	obstacles[0] == obstacles[n] == 0


class Solution:
    def minSideJumps(self, obstacles: List[int]) -> int:
        
        """
        # TLE Recursion DP
        @cache
        def dp(curr_lane = 2, point = 0):
            if point == len(obstacles)-1:
                return 0
            if obstacles[point+1] == curr_lane:
                return min(dp(lane, point+1) for lane in range(1, 4) if obstacles[point+1] != lane and obstacles[point]!=lane) + 1
            
            return dp(curr_lane, point+1)
        
        
        return dp()
            
        """
        
        n = len(obstacles)        
        dp = [[0, 0, 0, 0] for _ in range(n)]
        
        for point in range(n-2, -1, -1):
            for curr_lane in range(4):
                if obstacles[point+1] == curr_lane:
                    dp[point][curr_lane] = min(dp[point+1][lane] for lane in range(1, 4) if obstacles[point+1] != lane and obstacles[point]!=lane) + 1
                else:
                    dp[point][curr_lane] = dp[point+1][curr_lane]
                    
        return dp[0][2]
class Solution {
    public int minSideJumps(int[] obstacles) {
        int[] dp = new int[]{1, 0, 1};
        for(int i=1; i<obstacles.length; i++){
            switch(obstacles[i]){
                case 0:
                    dp[0] = min(dp[0], dp[1]+1, dp[2]+1);
                    dp[1] = min(dp[0]+1, dp[1], dp[2]+1);
                    dp[2] = min(dp[0]+1, dp[1]+1, dp[2]);
                    break;
                case 1:
                    dp[0] = Integer.MAX_VALUE;
                    dp[1] = min(dp[1], dp[2]+1);
                    dp[2] = min(dp[1]+1, dp[2]);
                    break;
                case 2:
                    dp[0] = min(dp[0], dp[2]+1);
                    dp[1] = Integer.MAX_VALUE;
                    dp[2] = min(dp[0]+1, dp[2]);
                    break;
                case 3:
                    dp[0] = min(dp[0], dp[1]+1);
                    dp[1] = min(dp[0]+1, dp[1]);
                    dp[2] = Integer.MAX_VALUE;
                    break;
            }
        }
        return min(dp[0], dp[1], dp[2]);
    }
    
    int min(int... vals){
        int min = Integer.MAX_VALUE;
        for(int val: vals){
            if(val>=0) min = Math.min(min, val);
        }
        return min;
    }
}
class Solution {
public:
    int func(int i,int l,vector<int>&obstacles,vector<vector<int>>&dp){
        if(i==obstacles.size()-2){
            if(obstacles[i+1]==l)return 1;
            return 0;
        }

        if(dp[i][l]!=-1)return dp[i][l];

        if(obstacles[i+1]!=l){
            return dp[i][l] = func(i+1,l,obstacles,dp);
        }

    
        int b=INT_MAX;
        for(int j=1;j<=3;j++){
            if(l==j)continue;
            if(obstacles[i]==j)continue;
            b=min(b,1+func(i,j,obstacles,dp));
        }
    

        return dp[i][l] = b;
    }

    int minSideJumps(vector<int>& obstacles) {
        int n=obstacles.size();
        vector<vector<int>>dp(n,vector<int>(4,-1));
        return func(0,2,obstacles,dp);
    }
};
var minSideJumps = function(obstacles) {
    // create a dp cache for tabulation
    const dp = [...obstacles].map(() => new Array(4).fill(Infinity));
    
    // initialize the first positions
    dp[0][2] = 0;
    for (const lane of [1,3]) {
        if (obstacles[0] === lane) continue;
        dp[0][lane] = 1;
    }

    // for every index we will do the following
    for (let i = 1; i < obstacles.length; i++) {
        
        // first we find the best way to get to this position from the previous index
        for (let nextLane = 1; nextLane <= 3; nextLane++) {
            if (obstacles[i] === nextLane) continue;
            dp[i][nextLane] = dp[i - 1][nextLane]
        }
        
        // then we find the best way to get to this position from the current index;
        for (let nextLane = 1; nextLane <= 3; nextLane++) {
            for (let prevLane = 1; prevLane <= 3; prevLane++) {
                if (prevLane === nextLane) continue;
                if (obstacles[i] === nextLane) continue;
                dp[i][nextLane] = Math.min(dp[i][nextLane], dp[i][prevLane] + 1)
            }
        }
    }

    // return the best result after reaching the end
    return Math.min(...dp[dp.length - 1])
};
Minimum Sideway Jumps