Algo-Assignment-4-DP-/14.py at main · Lomesh-AI/Algo-Assignment-4-DP- · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
from bisect import bisect_right

class Solution:
    def canCross(self, stones: List[int]) -> bool:
        n = len(stones)
        dp = {}

        def helper(ind, last_jump):
            if ind == n - 1:
                return True

            if (ind, last_jump) in dp:
                return dp[(ind, last_jump)]

            one_less_jump = False
            if last_jump > 1:
                index = bisect_right(stones, stones[ind] + last_jump - 1)
                if index - 1> ind and stones[index - 1] == stones[ind] + last_jump - 1:
                    one_less_jump = True and helper(index - 1, last_jump - 1)

            same_jump = False
            index = bisect_right(stones, stones[ind] + last_jump)
            if index - 1 > ind and stones[index - 1] == stones[ind] + last_jump:
                same_jump = True and helper(index - 1, last_jump)

            one_ahead_jump = False
            index = bisect_right(stones, stones[ind] + last_jump + 1)
            if index - 1 > ind and stones[index - 1] == stones[ind] + last_jump + 1:
                one_ahead_jump = True and helper(index - 1, last_jump+1)

            dp[(ind, last_jump)] = one_less_jump or same_jump or one_ahead_jump
            return dp[(ind, last_jump)]

        if stones[1] != 1:
            return False

        return helper(1, 1)