Solving Questions With Brainpower

How it works

Instead of recursion, we can fill a DP table iteratively from right to left. For each question, we compute the maximum points achievable starting from that position. Working backwards ensures that when we process question i, we already know the best outcomes for all questions after it.

Steps

1. Create a dp array of size n + 1, initialized to 0.
2. Iterate from the last question to the first (right to left).
3. For each question at index i:
   • Calculate the points if we solve it: points[i] + dp[i + 1 + brainpower[i]] (or 0 if out of bounds).
   • Calculate the points if we skip it: dp[i + 1].
   • Set dp[i] to the maximum of these two values.
4. Return dp[0], which contains the maximum points starting from the first question.

Complexity

• Time complexity: O(n)
• Space complexity: O(n)

Things to watch for

Integer Overflow with Point Accumulation

The points can accumulate to values exceeding 32-bit integer limits. When summing points across many questions, the result may overflow int. Always use long or long long for the DP array and return type to handle large cumulative values safely.

Incorrect Jump Calculation After Solving a Question

After solving question i, you must skip to question i + 1 + brainpower[i], not i + brainpower[i]. The +1 accounts for moving past the current question before skipping the required number. Missing this causes you to land on a question you should have skipped.

Wrong Iteration Direction in Bottom-Up DP

The bottom-up approach must iterate from the last question to the first (right to left). Iterating left to right means dp[i+1] has not been computed yet when you need it. Always use a reverse loop: for i in range(n-1, -1, -1) in Python or for (int i = n-1; i >= 0; i--) in other languages.

from typing import List

class Solution:
    def mostPoints(self, questions: List[List[int]]) -> int:
        dp = {}

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

class Solution {
public:
    long long mostPoints(vector<vector<int>>& questions) {
        int n = questions.size();
        vector<long long> dp(n + 1, 0);

        for (int i = n - 1; i >= 0; i--) {
            dp[i] = max(
                (long long)questions[i][0] + (i + 1 + questions[i][1] < n ? dp[i + 1 + questions[i][1]] : 0),
                dp[i + 1]
            );
        }
        return dp[0];
    }
};