Posted on 2023-08-27 16:33
Uriel 閱讀(50)
評論(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