讨论/《深度优先搜索》 - 练习:青蛙过河/
《深度优先搜索》 - 练习:青蛙过河
共 1 个回复
class Solution:
    def canCross(self, ss: List[int]) -> bool:
        for i in range(1,len(ss)): # 预处理剪枝
            if ss[i] > i + ss[i-1]:
                return False
        if len(ss) < 2: return True
        T = ss[-1]
        ss = set(ss)
        @functools.lru_cache(None)
        def dfs(idx, pst):
            if idx == T: return True
            ds = [-1,0,1]
            for d in ds:
                nst = pst + d
                if nst and idx + nst in ss and dfs(idx + nst, nst):
                    return True
            return False
        return dfs(0, 0)