Frog Jump

这是一道看起来是个动态规划的题，实际上解题思路更接近于BFS，因为可以用一个dict当做哈希表先将每个有石头的点提前记录在dict中，然后再重头进行遍历，每一个dict的key对应的都是一个set，记录跳到这个石子上所有可能的步数，然后每次拿出这个key对应的set里面的元素分别对k-1，k，k+1进行搜索，一是跳跃值距离是否为正数，二是判断以当前石头为基点加上这个跳跃步数是否能跳到另一个石头上（利用哈希表进行O(1)查询） 下面是代码

class Solution(object):
    def canCross(self, stones):
        """
        :type stones: List[int]
        :rtype: bool
        """
        n = len(stones)
        if n == 2:
            return stones[1] == 1

        dp = {}
        for stone in stones:
            dp[stone] = set([])
        dp[stones[0]].add(0)

        for stone in stones:
            for dis in dp[stone]:
                if dis - 1 > 0 and stone + dis - 1 in dp:
                    dp[stone + dis - 1].add(dis - 1)
                if dis > 0 and stone + dis in dp:
                    dp[stone + dis].add(dis)
                if dis + 1 > 0 and stone + dis + 1 in dp:
                    dp[stone + dis + 1].add(dis + 1)

        return len(dp[stones[-1]]) > 0