Untitled

mail@pastecode.io avatar
unknown
plain_text
a year ago
871 B
1
Indexable
Never
class Solution:
    def canCross(self, stones: List[int]) -> bool:
        if(stones[1]-stones[0]!=1):
            return False
        if(len(stones)==2):
            if stones[0]==0 and stones[1]==1:
                return True
        dp={}
        def cross(stones,curr,k,i):
            if curr>stones[len(stones)-1]:
                return False
            if curr==stones[len(stones)-1]:
                return True
            if (curr,k) in dp:
                return dp[(curr,k)]
            if curr in stones[i:]:
                dp[(curr+k-1,k-1)]=cross(stones,curr+k-1,k-1,i+1)
                dp[(curr+k,k)]=cross(stones,curr+k,k,i+1)
                dp[(curr+k+1,k+1)]=cross(stones,curr+k+1,k+1,i+1)
            else:
                return False
        cross(stones,stones[1],1,1)
        return any(value for value in dp.values())