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

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

<ul>
	<li>For example, if <code>obstacles[2] == 1</code>, then there is an obstacle on lane 1 at point 2.</li>
</ul>

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

<ul>
	<li>For example, the frog can jump from lane 3 at point 3 to lane 1 at point 3.</li>
</ul>

<p>Return<em> the <strong>minimum number of side jumps</strong> the frog needs to reach <strong>any lane</strong> at point n starting from lane <code>2</code> at point 0.</em></p>

<p><strong>Note:</strong> There will be no obstacles on points <code>0</code> and <code>n</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/03/25/ic234-q3-ex1.png" style="width: 500px; height: 244px;" />
<pre>
<strong>Input:</strong> obstacles = [0,1,2,3,0]
<strong>Output:</strong> 2 
<strong>Explanation:</strong> 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).
</pre>

<p><strong class="example">Example 2:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/03/25/ic234-q3-ex2.png" style="width: 500px; height: 196px;" />
<pre>
<strong>Input:</strong> obstacles = [0,1,1,3,3,0]
<strong>Output:</strong> 0
<strong>Explanation:</strong> There are no obstacles on lane 2. No side jumps are required.
</pre>

<p><strong class="example">Example 3:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/03/25/ic234-q3-ex3.png" style="width: 500px; height: 196px;" />
<pre>
<strong>Input:</strong> obstacles = [0,2,1,0,3,0]
<strong>Output:</strong> 2
<strong>Explanation:</strong> The optimal solution is shown by the arrows above. There are 2 side jumps.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>obstacles.length == n + 1</code></li>
	<li><code>1 &lt;= n &lt;= 5 * 10<sup>5</sup></code></li>
	<li><code>0 &lt;= obstacles[i] &lt;= 3</code></li>
	<li><code>obstacles[0] == obstacles[n] == 0</code></li>
</ul>


def f1(obs, idx, lane):
    # print(idx, lane)
    if idx == len(obs)-1:
        return 0 

    min_side_jumps = float("inf")
    # print(idx, obs, len(obs), idx >= len(obs))
    if obs[idx] != 1 and obs[idx+1] != 1:
        if lane == 1:
            extra_cost = 0
        else:
            extra_cost = 1
        min_side_jumps = min(min_side_jumps, extra_cost + f1(obs, idx+1, 1))
    if obs[idx] != 2 and obs[idx+1] != 2:
        if lane == 2:
            extra_cost = 0
        else:
            extra_cost = 1
        min_side_jumps = min(min_side_jumps, extra_cost + f1(obs, idx+1, 2))
    if obs[idx] != 3 and obs[idx+1] != 3:
        if lane == 3:
            extra_cost = 0
        else:
            extra_cost = 1
        min_side_jumps = min(min_side_jumps, extra_cost + f1(obs, idx+1, 3))

    return min_side_jumps

def f2(obs, idx, lane, DP):
    # print(idx, lane)
    if idx == len(obs)-1:
        return 0 

    if DP[idx][lane] != -1:
        return DP[idx][lane]

    min_side_jumps = float("inf")
    # print(idx, obs, len(obs), idx >= len(obs))
    if obs[idx] != 1 and obs[idx+1] != 1:
        if lane == 1:
            extra_cost = 0
        else:
            extra_cost = 1
        min_side_jumps = min(min_side_jumps, extra_cost + f2(obs, idx+1, 1, DP))
    if obs[idx] != 2 and obs[idx+1] != 2:
        if lane == 2:
            extra_cost = 0
        else:
            extra_cost = 1
        min_side_jumps = min(min_side_jumps, extra_cost + f2(obs, idx+1, 2, DP))
    if obs[idx] != 3 and obs[idx+1] != 3:
        if lane == 3:
            extra_cost = 0
        else:
            extra_cost = 1
        min_side_jumps = min(min_side_jumps, extra_cost + f2(obs, idx+1, 3, DP))

    DP[idx][lane] = min_side_jumps
    return min_side_jumps

def f3(obs):
    DP = [[0 for _ in range(4)] for _ in range(len(obs))]

    for idx in range(len(obs)-2, -1, -1):
        for lane in range(1, 4):
            min_side_jumps = float("inf")

            if obs[idx] != 1 and obs[idx+1] != 1:
                if lane == 1:
                    extra_cost = 0
                else:
                    extra_cost = 1
                min_side_jumps = min(min_side_jumps, extra_cost + DP[idx+1][1])
            if obs[idx] != 2 and obs[idx+1] != 2:
                if lane == 2:
                    extra_cost = 0
                else:
                    extra_cost = 1
                min_side_jumps = min(min_side_jumps, extra_cost + DP[idx+1][2])
            if obs[idx] != 3 and obs[idx+1] != 3:
                if lane == 3:
                    extra_cost = 0
                else:
                    extra_cost = 1
                min_side_jumps = min(min_side_jumps, extra_cost + DP[idx+1][3])

            DP[idx][lane] = min_side_jumps

    return DP[0][2]

def f4(obs):
    "sp op"

    nex_col = [0 for _ in range(4)] 
    cur_col = [0 for _ in range(4)] 

    for idx in range(len(obs)-2, -1, -1):
        for lane in range(1, 4):
            min_side_jumps = float("inf")

            if obs[idx] != 1 and obs[idx+1] != 1:
                if lane == 1:
                    extra_cost = 0
                else:
                    extra_cost = 1
                min_side_jumps = min(min_side_jumps, extra_cost + nex_col[1])
            if obs[idx] != 2 and obs[idx+1] != 2:
                if lane == 2:
                    extra_cost = 0
                else:
                    extra_cost = 1
                min_side_jumps = min(min_side_jumps, extra_cost + nex_col[2])
            if obs[idx] != 3 and obs[idx+1] != 3:
                if lane == 3:
                    extra_cost = 0
                else:
                    extra_cost = 1
                min_side_jumps = min(min_side_jumps, extra_cost + nex_col[3])

            cur_col[lane] = min_side_jumps
        cur_col, nex_col = nex_col, cur_col

    if len(obs)%2 == 0:
        return cur_col[2]
    else:
        return nex_col[2]

class Solution:
    def minSideJumps(self, obs: List[int]) -> int:
        # return f1(obs, idx=0, lane=2)

        # DP = [[-1 for _ in range(4)] for _ in range(len(obs))]
        # return f2(obs, idx=0, lane=2, DP=DP)

        # return f3(obs)

        return f4(obs)
32299