LeetCode题解(0403)：青蛙过河(Python)

题目：​​原题链接​​（困难）

标签：动态规划

解法	时间复杂度	空间复杂度	执行用时
Ans 1 (Python)	204ms (71.62%)
Ans 2 (Python)

class Solution:
    def canCross(self, stones: List[int]) -> bool:
        size = len(stones)
        index = {stone: i for i, stone in enumerate(stones)}

        if stones[1] - stones[0] != 1:
            return False

        dp = [set() for _ in range(size)]

        dp[1].add(stones[1] - stones[0])

        for i in range(1, size):
            stone = stones[i]
            for step in dp[i]:
                if stone + step + 1 in index:
                    dp[index[stone + step + 1]].add(step + 1)
                if stone + step in index:
                    dp[index[stone + step]].add(step)
                if step > 1 and stone + step - 1 in index:
                    dp[index[stone + step - 1]].add(step - 1)

        return len(dp[-1]) > 0