23.05.12 Today’s Leetcode

2140. Solving Questions With Brainpower (medium)

DP + Memoization Approach : TLE at 48 / 54

class Solution:
    def mostPoints(self, questions: List[List[int]]) -> int:
        n = len(questions)

        @functools.lru_cache(None)
        def dfs(cur, point):
            if cur >= n:
                return point
            
            p, b = questions[cur]

            temp = 0
            temp = max(temp, dfs(cur + b + 1, point + p))
            temp = max(temp, dfs(cur + 1, point))
            return temp

        return dfs(0, 0)

top-down DP

class Solution:
    def mostPoints(self, questions: List[List[int]]) -> int:
        n = len(questions)
        dp = [0] * (n + 1)
        for i in range(n - 1, -1, -1):
            p, b = questions[i]
            nextQuestion = min(n, i + b + 1)
            dp[i] = max(dp[i + 1], p + dp[nextQuestion])

        return dp[0]

403. Frog Jump (hard)

DFS Approach : TLE at 16/52

class Solution:
    def canCross(self, stones: List[int]) -> bool:

        n = len(stones)

        def dfs(cur, jump):
            if cur == n - 1:
                return True

            for i in range(cur + 1, n):
                diff = stones[i] - stones[cur]
                if diff >= jump - 1 and diff <= jump + 1:
                    if dfs(i, diff):
                        return True
                
            return False

        return dfs(0, 0)

class Solution:
    def canCross(self, stones: List[int]) -> bool:
        # Create a dictionary to store the set of possible jumps for each stone
        jumps = {}
        for stone in stones:
            jumps[stone] = set()

        # Initialize the set of possible jumps for the first stone with 1
        jumps[0].add(1)

        # Iterate through each stone
        for stone in stones:
            # Iterate through the set of possible jumps for the current stone
            for jump in jumps[stone]:
                # Check if the stone at the current position plus the jump size is in the list of stones
                next_stone = stone + jump
                if next_stone in jumps:
                    # Add the possible jump sizes to the set of possible jumps for the stone at the next position
                    jumps[next_stone].add(jump)
                    if jump > 1:
                        jumps[next_stone].add(jump - 1)
                    jumps[next_stone].add(jump + 1)

        # Check if the last stone has a non-empty set of possible jumps
        return len(jumps[stones[-1]]) > 0