Posted on 2023-08-27 16:33
Uriel 阅读(34)
评论(0) 编辑 收藏 引用 所属分类:
DP 、
闲来无事重切Leet Code 、
Hash
给出一堆数字stones代表stones[i]处有石子，青蛙从第一个石子处出发，第一次必须跳1步，之后每次可以跳的步数为k-1~k+1，k为前一步跳的步数，问是否可达最后一个石子。
O(n^2)的dp，用dict存储stones位置，dict的value为跳到这个位置所有可能的上一步的长度，参考了Discussion -> https://leetcode.com/problems/frog-jump/solutions/3964842/python3-solution/
1 #403
2 #Runtime: 191 ms (Beats 50.94%)
3 #Memory: 14.9 MB (Beats 79.25%)
4
5 class Solution(object):
6 def canCross(self, stones):
7 """
8 :type stones: List[int]
9 :rtype: bool
10 """
11 n = len(stones)
12 dp = {stone:set() for stone in stones}
13 dp[0].add(0)
14 for i in range(n):
15 for j in dp[stones[i]]:
16 for d in range(j - 1, j + 2):
17 if d and stones[i] + d in dp:
18 dp[stones[i] + d].add(d)
19 return len(dp[stones[-1]]) > 0