Minimum Sideway Jumps LeetCode solution in Python

1
class Solution:
2
    def minSideJumps(self, obstacles: List[int]) -> int:
3
        """
4
        # TLE Recursion DP
5
        @cache
6
        def dp(curr_lane = 2, point = 0):
7
            if point == len(obstacles)-1:
8
                return 0
9
            if obstacles[point+1] == curr_lane:
10
                return min(dp(lane, point+1) for lane in range(1, 4) if obstacles[point+1] != lane and obstacles[point]!=lane) + 1
11

12
            return dp(curr_lane, point+1)
13

14

15
        return dp()
16

17
        """
18

19
        n = len(obstacles)
20
        dp = [[0, 0, 0, 0] for _ in range(n)]
21

22
        for point in range(n - 2, -1, -1):
23
            for curr_lane in range(4):
24
                if obstacles[point + 1] == curr_lane:
25
                    dp[point][curr_lane] = (
26
                        min(
27
                            dp[point + 1][lane]
28
                            for lane in range(1, 4)
29
                            if obstacles[point + 1] != lane and obstacles[point] != lane
30
                        )
31
                        + 1
32
                    )
33
                else:
34
                    dp[point][curr_lane] = dp[point + 1][curr_lane]
35

36
        return dp[0][2]