Skip to content

2140. Solving Questions With Brainpower 👍

  • Time: $O(n)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution {
 public:
  long long mostPoints(vector<vector<int>>& questions) {
    const int n = questions.size();
    // dp[i] := the maximum points starting from questions[i]
    vector<long> dp(n + 1);

    for (int i = n - 1; i >= 0; --i) {
      const int points = questions[i][0];
      const int brainpower = questions[i][1];
      const int nextIndex = i + brainpower + 1;
      const long nextPoints = nextIndex < n ? dp[nextIndex] : 0;
      dp[i] = max(points + nextPoints, dp[i + 1]);
    }

    return dp[0];
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution {
  public long mostPoints(int[][] questions) {
    final int n = questions.length;
    // dp[i] := the maximum points starting from questions[i]
    long[] dp = new long[n + 1];

    for (int i = n - 1; i >= 0; --i) {
      final int points = questions[i][0];
      final int brainpower = questions[i][1];
      final int nextIndex = i + brainpower + 1;
      final long nextPoints = nextIndex < n ? dp[nextIndex] : 0;
      dp[i] = Math.max(points + nextPoints, dp[i + 1]);
    }

    return dp[0];
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution:
  def mostPoints(self, questions: list[list[int]]) -> int:
    n = len(questions)
    # dp[i] := the maximum points starting from questions[i]
    dp = [0] * (n + 1)

    for i in reversed(range(n)):
      points, brainpower = questions[i]
      nextIndex = i + brainpower + 1
      nextPoints = dp[nextIndex] if nextIndex < n else 0
      dp[i] = max(points + nextPoints, dp[i + 1])

    return dp[0]