Problem Summary

You are given a 2D array questions, where each entry is:

questions[i] = [points_i, brainpower_i]

If you solve question i:

• You earn points_i.
• You must skip the next brainpower_i questions.

If you skip question i, you earn nothing and simply move to the next one.

Your task is to compute the maximum points you can earn.

Example
Input:

questions = [[3,2], [4,3], [4,4], [2,5]]

Output:

5

Explanation:
You can solve question 0 (earn 3), then must skip questions 1 and 2, then solve question 3 (earn 2).
Total = 3 + 2 = 5.

Constraints

• 1 ≤ questions.length ≤ 10⁵
• 1 ≤ points ≤ 10⁵
• 0 ≤ brainpower ≤ questions.length

This requires an efficient DP solution.

---

Approach (Simple English)

This is a classic Dynamic Programming problem where at each index you have two choices:

1. Solve the current question:
   • Earn points[i]
   • Jump to i + brainpower[i] + 1
2. Skip the current question:
   • Move to i + 1

We choose whichever option gives more points.

Key Idea

Define:

dp[i] = maximum points that can be earned from question i to the end

Then:

solve = points[i] + dp[i + brainpower[i] + 1]
skip = dp[i + 1]
dp[i] = max(solve, skip)

We compute dp backwards from the end.

Why This Works

Each question’s best result depends on future choices.
By computing from the last question backward, all future results are already known.

Steps

1. Create DP array of length n+1 initialized to zero.
2. Iterate i from n−1 down to 0:
   • compute solve option
   • compute skip option
   • dp[i] = max(solve, skip)
3. Return dp[0]

Time Complexity

O(n) — single backward pass.

Space Complexity

O(n)

---

Java Code (Bottom-Up Dynamic Programming)

class Solution {
    public long mostPoints(int[][] questions) {

        int n = questions.length;
        long[] dp = new long[n + 1];

        for (int i = n - 1; i >= 0; i--) {
            int points = questions[i][0];
            int skip = questions[i][1];

            long solve = points;
            int nextIndex = i + skip + 1;
            if (nextIndex < n) {
                solve += dp[nextIndex];
            }

            long skipOption = dp[i + 1];

            dp[i] = Math.max(solve, skipOption);
        }

        return dp[0];
    }
}

Notes:

• Use long because points can be large and accumulate across many solves.

---

Alternative Approach: Recursion + Memoization

This top-down form expresses the formula directly.

Recurrence

dfs(i) = max(
    points[i] + dfs(i + brainpower[i] + 1),
    dfs(i + 1)
)

Memoize results to avoid recomputation.

Java Code (Recursive Version)

class Solution {

    private long[] memo;

    public long mostPoints(int[][] questions) {
        int n = questions.length;
        memo = new long[n];
        Arrays.fill(memo, -1);
        return dfs(0, questions);
    }

    private long dfs(int i, int[][] questions) {
        if (i >= questions.length) return 0;
        if (memo[i] != -1) return memo[i];

        long solve = questions[i][0] + dfs(i + questions[i][1] + 1, questions);
        long skip = dfs(i + 1, questions);

        return memo[i] = Math.max(solve, skip);
    }
}

---

Dry Run (Bottom-Up DP)

Input:

questions = [[3,2], [4,3], [4,4], [2,5]]

Index mapping:

• q0 = [3,2]
• q1 = [4,3]
• q2 = [4,4]
• q3 = [2,5]

dp array length = 5 (index 0..4)

Start from i = 3:

i = 3

points = 2
skip = 5
solve = 2 + dp[3 + 5 + 1] = 2 + dp[9] = 2
skipOption = dp[4] = 0
dp[3] = max(2, 0) = 2

i = 2

points = 4
skip = 4
solve = 4 + dp[2 + 4 + 1] = 4 + dp[7] = 4
skipOption = dp[3] = 2
dp[2] = max(4, 2) = 4

i = 1

points = 4
skip = 3
solve = 4 + dp[1 + 3 + 1] = 4 + dp[5] = 4
skipOption = dp[2] = 4
dp[1] = max(4, 4) = 4

i = 0

points = 3
skip = 2
solve = 3 + dp[0 + 2 + 1] = 3 + dp[3] = 3 + 2 = 5
skipOption = dp[1] = 4
dp[0] = max(5, 4) = 5

Final result = dp[0] = 5