8.21 - hard - 78

403. Frog Jump
首先做出来一个TLE的版本，因为这里面要search三种情况，可以用记忆化搜索来做。

class Solution(object):
    def canCross(self, stones):
        """
        :type stones: List[int]
        :rtype: bool
        """
        if len(stones) <= 1:
            return True
        # dp[i][j] 通过一次跳j步，可以跳到stone i上
        dp = [[False for _ in range(2*len(stones))] for _ in range(len(stones))]
        dp[0][0] = True
        if stones[1] != 1:
            return False
        dp[1][1] = True
        for i in range(2, len(stones)):
            for k in range(1, i):
                for j in range(1, 2*len(stones)-1):
                    if dp[k][j]: #如果前一块石头用了j步可以达到
                        dp[i][j] = dp[i][j] or (stones[i] - stones[k]) == j
                        dp[i][j-1] = dp[i][j-1] or (stones[i] - stones[k]) == j - 1
                        dp[i][j+1] = dp[i][j+1] or (stones[i] - stones[k]) == j + 1
        #print dp[5]
        return any(dp[len(stones)-1])

class Solution(object):
    def canCross(self, stones):
        """
        :type stones: List[int]
        :rtype: bool
        """
        self.memo = set()
        target = stones[-1]
        stones = set(stones)

        res = self.bt(stones, 1, 1, target)
        return res

    def bt(self, stones, cur, speed, target):
        # check memo
        if (cur, speed) in self.memo:
            return False

        if cur==target:
            return True
        
        if cur>target or cur<0 or speed<=0 or cur not in stones:
            return False
        # dfs
        candidate = [speed-1, speed, speed+1]
        for c in candidate:
            if (cur + c) in stones:
                if self.bt(stones, cur+c, c, target):
                    return True

        self.memo.add((cur,speed))
        return False