Sponsored
Sponsored
This approach leverages dynamic programming to solve the problem. You create a DP array where each element dp[i] represents the maximum points that can be earned starting from question i to the last question. You decide whether to solve or skip a question based on the potential points you can earn. The solution is filled backward, starting from the last question.
Time Complexity: O(n)
Space Complexity: O(n)
1#include <vector>
2using namespace std;
3
4int maxPoints(vector<vector<int>>& questions) {
5 int n = questions.size();
6 vector<int> dp(n + 1, 0);
7 for (int i = n - 1; i >= 0; --i) {
8 int solve = questions[i][0] + (i + 1 + questions[i][1] < n ? dp[i + 1 + questions[i][1]] : 0);
9 int skip = dp[i + 1];
10 dp[i] = max(solve, skip);
11 }
12 return dp[0];
13}The C++ solution works similarly to the Python solution. It uses a vector as a dynamic array to maintain the max points from the current index to the last. Just like before, it iterates backward, calculating the best option between solving and skipping for each question. It stores results in the vector, and returns the maximum points from the first question.
This approach uses recursion with memoization to avoid recomputing results for overlapping subproblems. It recursively decides the maximum points by considering both solving and skipping options for each question, and stores results in a memoization array for reuse. This provides an efficient way to solve the problem since it avoids redundant calculations.
Time Complexity: O(n)
Space Complexity: O(n)
1
This C implementation makes use of a recursive function dfs that takes question index i and applies memoization to keep previously calculated results. The `memo` array serves as a caching store to prevent redundant computations. Each call evaluates solving vs skipping the current question, and chooses the option with the highest potential points. The function finally returns the maximum value possible.