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
