Description

Submission

class Solution {
    int dp[3][500005];
public:
    int minSideJumps(vector<int>& obstacles) {
        int n = obstacles.size();
        obstacles.insert(obstacles.begin(), 0);

        dp[0][0] = 1;
        dp[2][0] = 1;

        for(int j = 1; j <= n; ++j) {
            for(int i  = 0; i < 3; ++i) {
                if(obstacles[j] == i + 1) dp[i][j] = INT_MAX / 2;
                else dp[i][j] = dp[i][j-1];
            }

            if(obstacles[j] != 1) dp[0][j] = min(dp[0][j], min(dp[1][j], dp[2][j]) + 1);
            if(obstacles[j] != 2) dp[1][j] = min(dp[1][j], min(dp[0][j], dp[2][j]) + 1);
            if(obstacles[j] != 3) dp[2][j] = min(dp[2][j], min(dp[0][j], dp[1][j]) + 1);
        }

        return min(dp[0][n], min(dp[1][n], dp[2][n]));
    }
};