2140. Solving Questions With Brainpower

Intuition

This is a classic Dynamic Programming problem where at each question, we decide between:

• Solving it (and skipping the next brainpower[i] questions),

• Or skipping it and checking the next one.

We use memoization to avoid recalculating the maximum points for the same index again.

Complexity

Space Complexity	Time Complexity
$\text{O}(N)$	$\text{O}(N)$

Code

// Memoization array to store max points from each index
long[] memo;

// Recursive DP function to compute maximum points from question `index`
long pointsCalc(int[][] questions, int index) {
    // Base case: if index is out of bounds, no points can be earned
    if (index >= questions.length) {
        return 0;
    }

    // If result already computed, return it
    if (memo[index] != -1) return memo[index];

    // Option 1: Skip the current question and go to the next one
    long skipPoints = pointsCalc(questions, index + 1);

    // Option 2: Solve the current question
    // Add its points and skip the next `brainpower` questions
    long solvePoints = questions[index][0] + pointsCalc(questions, index + 1 + questions[index][1]);

    // Store the maximum of both choices in memo and return it
    memo[index] = Math.max(skipPoints, solvePoints);
    return memo[index];
}

public long mostPoints(int[][] questions) {
    // Initialize memoization array with -1
    memo = new long[questions.length + 1];
    Arrays.fill(memo, -1);

    // Start solving from the 0th question
    return pointsCalc(questions, 0);
}