Hi There,
I have been LeetCoding consistenly and started solving DP problems since last week.
I can come up with a recursive solution relatively easily,
but when I try to convert it into Iterative Algorithm, my brain just gets freezed.
And also analysing time-space complexity for recursive algorithms also seems pretty hard.
Need Help!
Any advice, resources are appreciated ✌️.
This is my approach of Frog Game using Top-Down Memoization
class Solution:
def canCross(self, stones: List[int]) -> bool:
s = set(stones)
last = stones[-1]
# TOP DOWN RECURSIVE
d = {}
def dfs(pos, k):
if pos == 0:
return dfs(1, 1)
if pos not in s:
return False
if (pos, k) in d:
return d[(pos, k)]
if pos == last:
return True
out = False
for nxt in range(k - 1, k + 2):
if pos + nxt <= pos:
continue
out = out or dfs(pos + nxt, nxt)
d[(pos, k)] = out
return out
return dfs(0, 1)