NEED HELP figuring out BOTTOM-UP DP

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)
Comments (0)