2140. Solving Questions With Brainpower

2140. Solving Questions With Brainpower

 

class Solution:
    def mostPoints(self, questions: List[List[int]]) -> int:
        # brainpower[i]는 해당 문제를 푼 후 건너뛰어야 하는 문제의 개수를 의미
        # 즉, 문제 i를 풀기로 선택하면, 
        # 그 다음 연속된 brainpower[i]개의 문제는 풀 수 없음
        n = len(questions)

        dp = [0] * (n+1)  # dp[i]는 질문 i부터 끝까지 얻을 수 있는 최대 점수

        for i in range(n - 1, -1, -1):  # 역순으로 순회
            point, brainpower = questions[i]
            
            # 현재 질문을 풀이한 경우와 건너뛴 경우 중 더 큰 값을 저장
            if i + brainpower + 1 < n:
                dp[i] = max(dp[i + 1], point + dp[i + brainpower + 1])
            else:
                dp[i] = max(dp[i + 1], point)

        return dp[0]  # 첫 번째 질문부터 얻을 수 있는 최대 점수 반환

 

최적화 (공간 복잡도 O(1)로 줄이기)

dp 배열 대신 두 개의 변수를 사용하여 공간을 절약할 수 있습니다:

class Solution:
    def mostPoints(self, questions: List[List[int]]) -> int:
        n = len(questions)
        next_dp, curr_dp = 0, 0  # 다음 상태와 현재 상태를 저장

        for i in range(n - 1, -1, -1):  # 역순으로 순회
            point, brainpower = questions[i]
            if i + brainpower + 1 < n:
                curr_dp = max(next_dp, point + dp[i + brainpower + 1])
            else:
                curr_dp = max(next_dp, point)
            next_dp = curr_dp  # 다음 상태 업데이트

        return curr_dp

 

https://youtu.be/D7TD_ArkfkA?si=Ij633n4xB8ZT6h_Q

 

class Solution:
    def mostPoints(self, questions: List[List[int]]) -> int:
        # brainpower[i]는 해당 문제를 푼 후 건너뛰어야 하는 문제의 개수를 의미
        # 즉, 문제 i를 풀기로 선택하면, 
        # 그 다음 연속된 brainpower[i]개의 문제는 풀 수 없음
        dp = {}

        def dfs(i):
            if i >= len(questions):
                return 0

            if i in dp:
                return dp[i]

            dp[i] = max(
                dfs(i+1), # skip question
                questions[i][0] + dfs(i + 1 + questions[i][1]) # solve current question
            )
            return dp[i] 

        return dfs(0)

 

최적화

 

class Solution:
    def mostPoints(self, questions: List[List[int]]) -> int:
        # brainpower[i]는 해당 문제를 푼 후 건너뛰어야 하는 문제의 개수를 의미
        # 즉, 문제 i를 풀기로 선택하면, 
        # 그 다음 연속된 brainpower[i]개의 문제는 풀 수 없음

        # Time: O(N)
        # Space: O(N)
        dp = {}

        for i in range(len(questions)-1, -1, -1): # reversed order
            dp[i] = max(questions[i][0] + dp.get(i + 1 + questions[i][1], 0), # include 
                        dp.get(i+1, 0)) # skip
        return dp[0]