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 <stdio.h>
2#include <stdlib.h>
3
4int maxPoints(int** questions, int questionsSize) {
5 int* dp = (int*)calloc(questionsSize + 1, sizeof(int));
6 for (int i = questionsSize - 1; i >= 0; i--) {
7 int solve = questions[i][0] + ((i + 1 + questions[i][1] < questionsSize) ? dp[i + 1 + questions[i][1]] : 0);
8 int skip = dp[i + 1];
9 dp[i] = (solve > skip) ? solve : skip;
10 }
11 int result = dp[0];
12 free(dp);
13 return result;
14}This C code uses a dynamic programming approach similar to the Python version. It uses a pointer to an array, initialized with zero values, to store the maximum points from each question. The solution proceeds by iterating backward over the questions, computing whether to solve or skip each question, and stores the best result in the dp array. Finally, it returns the maximum points from the first question and frees the allocated memory.
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#include <unordered_map>
using namespace std;
int dfs(vector<vector<int>>& questions, int i, unordered_map<int, int>& memo) {
if (i >= questions.size()) return 0;
if (memo.count(i)) return memo[i];
int solve = questions[i][0] + dfs(questions, i + 1 + questions[i][1], memo);
int skip = dfs(questions, i + 1, memo);
memo[i] = max(solve, skip);
return memo[i];
}
int maxPoints(vector<vector<int>>& questions) {
unordered_map<int, int> memo;
return dfs(questions, 0, memo);
}In the C++ code, a recursive function dfs with memoization calculates the maximum points starting from each question. Memoization is implemented using a hashmap for caching results, which helps mitigate redundant operations by storing and reusing prior computations. The code evaluates points from solving or skipping and consistently chooses the option providing maximum points, finally returning results starting from the first question.