# 1824. Minimum Sideway Jumps
###### tags: `Leetcode` `Medium` `Dynamic Programming`
Link: https://leetcode.com/problems/minimum-sideway-jumps/
## 思路
三种状态 lane0, lane1, lane2
在计算dp[i][j]的时候(i代表position j代表lane)
首先要看当下三个lane有没有哪个有obstacle 如果有的话这个lane的值直接设为```Integer.MAX_VALUE```
对于每个obstacle的lane 两种可能性
1. 可以从dp[i-1][j]直接过去 ```dp[i][j] = dp[i-1][j]```
2. 在所有dp[i][j]里面挑选最小的方案，然后+1就可以用于更新其他的dp[i][j]
## Code

class Solution {
    public int minSideJumps(int[] obstacles) {
        int n = obstacles.length;
        int[][] dp = new int[n][3];
        dp[0][0] = 1;
        dp[0][2] = 1;
        for(int i=1; i<n; i++){
            dp[i] = dp[i-1].clone();
            if(obstacles[i]!=0){
                dp[i][obstacles[i]-1]=Integer.MAX_VALUE;
            }
            int minVal = dp[i][0];
            for(int j=0; j<3; j++){
                if(dp[i][j]!=Integer.MAX_VALUE && dp[i][j]<minVal){
                    minVal = dp[i][j];
                }
            }
            for(int j=0; j<3; j++){
                if(j==obstacles[i]-1) continue;
                if(dp[i][j]!=minVal) dp[i][j] = minVal+1;
            }
        }
        return Math.min(dp[n-1][0], Math.min(dp[n-1][1], dp[n-1][2]));
    }
}