2140. Solving Questions With Brainpower

MediumView on LeetCode

Array Dynamic Programming

Time: O(n)

Space: O(n)

Intuition

DP with 2 skips available. dp[i][j] = max points using j skips through question i.

Algorithm

1dp[i][0] = max(dp[i-1][0], dp[prev_earn][0] + points[i-1]) where prev_earn accounts for brainpower.
2dp[i][j] = max(dp[i-1][j], dp[prev_earn][j-1] + points[i-1], dp[i-1][j-1]) second option: skip this question costs 1 skip.

Common Pitfalls

•Brainpower of question i skips to question i + brainpower + 1. Track 0 and 1 (or 2) skips used.

2140.cs

// Approach: DP from right to left; for each question choose solve (skip next) or skip.
// Time: O(n) Space: O(n)

public class Solution
{
    private int numQuestions; // Total number of questions
    public long MostPoints(int[][] questions)
    {
        numQuestions = questions.Length; // Initialize number of questions
        long[] dp = new long[numQuestions]; // Initialize the cache array
        Array.Fill(dp, -1);
        return TopDown(0, dp, questions); // Start the depth-first search from the first question   
    }

    // Recursive method using Depth-First Search to calculate the maximum points
    private long TopDown(int index, long[] dp, int[][] questions)
    {
        if (index >= numQuestions) // Base case: if the index exceeds the number of questions
            return 0; // No more points can be earned, return 0

        if (dp[index] != -1)  // If the result for this index is already computed
            return dp[index]; // Return the cached result

        int points = questions[index][0]; // Points for the current question
        int bonus = questions[index][1]; // Bonus (number of questions to skip) for the current question

        // Recur in two scenarios: either answer the current question and jump over the bonus questions,
        // or move to the next question. Take the maximum of these two choices.
        return dp[index] = Math.Max(points + TopDown(index + bonus + 1, dp, questions), TopDown(index + 1, dp, questions));
    }
}

Was this solution helpful?