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)
1def maxPoints(questions):
2 n = len(questions)
3 dp = [0] * (n + 1)
4 for i in range(n - 1, -1, -1):
5 solve = questions[i][0] + dp[min(n, i + 1 + questions[i][1])]
6 skip = dp[i + 1]
7 dp[i] = max(solve, skip)
8 return dp[0]The code initializes a dp array with zeros of size n+1 where n is the number of questions. It iterates over the questions in reverse order, calculating the maximum possible points by considering either solving or skipping the current question. Finally, it returns the result stored in dp[0] which represents 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
public class Solution {
private int Dfs(int[][] questions, int i, Dictionary<int, int> memo) {
if (i >= questions.Length) return 0;
if (memo.ContainsKey(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] = System.Math.Max(solve, skip);
return memo[i];
}
public int MaxPoints(int[][] questions) {
var memo = new Dictionary<int, int>();
return Dfs(questions, 0, memo);
}
}Here, the C# implementation uses a recursive technique with memoization. It applies a dictionary for storing prior outcomes to circumvent replicating tasks. Recursive calls analyze solving and skipping choices, following which the memoization step guarantees reflection of the most rewarding computation. It subsequently outputs the maximum viable points for starting point zero.