Question

2140. Solving Questions With Brainpower

中文文档

Description

You are given a 0-indexed 2D integer array questions where questions[i] = [pointsi, brainpoweri].

The array describes the questions of an exam, where you have to process the questions in order (i.e., starting from question 0) and make a decision whether to solve or skip each question. Solving question i will earn you pointsi points but you will be unable to solve each of the next brainpoweri questions. If you skip question i, you get to make the decision on the next question.

• For example, given questions = [[3, 2], [4, 3], [4, 4], [2, 5]]:
  • If question 0 is solved, you will earn 3 points but you will be unable to solve questions 1 and 2.
  • If instead, question 0 is skipped and question 1 is solved, you will earn 4 points but you will be unable to solve questions 2 and 3.

Return _the maximum points you can earn for the exam_.

 

Example 1:

Input: questions = [[3,2],[4,3],[4,4],[2,5]]
Output: 5
Explanation: The maximum points can be earned by solving questions 0 and 3.
- Solve question 0: Earn 3 points, will be unable to solve the next 2 questions
- Unable to solve questions 1 and 2
- Solve question 3: Earn 2 points
Total points earned: 3 + 2 = 5. There is no other way to earn 5 or more points.

Example 2:

Input: questions = [[1,1],[2,2],[3,3],[4,4],[5,5]]
Output: 7
Explanation: The maximum points can be earned by solving questions 1 and 4.
- Skip question 0
- Solve question 1: Earn 2 points, will be unable to solve the next 2 questions
- Unable to solve questions 2 and 3
- Solve question 4: Earn 5 points
Total points earned: 2 + 5 = 7. There is no other way to earn 7 or more points.

 

Constraints:

• 1 <= questions.length <= 105
• questions[i].length == 2
• 1 <= pointsi, brainpoweri <= 105

Solutions

Solution 1

class Solution:
  def mostPoints(self, questions: List[List[int]]) -> int:
    @cache
    def dfs(i: int) -> int:
      if i >= len(questions):
        return 0
      p, b = questions[i]
      return max(p + dfs(i + b + 1), dfs(i + 1))

    return dfs(0)

class Solution {
  private int n;
  private Long[] f;
  private int[][] questions;

  public long mostPoints(int[][] questions) {
    n = questions.length;
    f = new Long[n];
    this.questions = questions;
    return dfs(0);
  }

  private long dfs(int i) {
    if (i >= n) {
      return 0;
    }
    if (f[i] != null) {
      return f[i];
    }
    int p = questions[i][0], b = questions[i][1];
    return f[i] = Math.max(p + dfs(i + b + 1), dfs(i + 1));
  }
}

class Solution {
public:
  long long mostPoints(vector<vector<int>>& questions) {
    int n = questions.size();
    long long f[n];
    memset(f, 0, sizeof(f));
    function<long long(int)> dfs = [&](int i) -> long long {
      if (i >= n) {
        return 0;
      }
      if (f[i]) {
        return f[i];
      }
      int p = questions[i][0], b = questions[i][1];
      return f[i] = max(p + dfs(i + b + 1), dfs(i + 1));
    };
    return dfs(0);
  }
};

func mostPoints(questions [][]int) int64 {
  n := len(questions)
  f := make([]int64, n)
  var dfs func(int) int64
  dfs = func(i int) int64 {
    if i >= n {
      return 0
    }
    if f[i] > 0 {
      return f[i]
    }
    p, b := questions[i][0], questions[i][1]
    f[i] = max(int64(p)+dfs(i+b+1), dfs(i+1))
    return f[i]
  }
  return dfs(0)
}

function mostPoints(questions: number[][]): number {
  const n = questions.length;
  const f = Array(n).fill(0);
  const dfs = (i: number): number => {
    if (i >= n) {
      return 0;
    }
    if (f[i] > 0) {
      return f[i];
    }
    const [p, b] = questions[i];
    return (f[i] = Math.max(p + dfs(i + b + 1), dfs(i + 1)));
  };
  return dfs(0);
}

Solution 2

class Solution:
  def mostPoints(self, questions: List[List[int]]) -> int:
    n = len(questions)
    f = [0] * (n + 1)
    for i in range(n - 1, -1, -1):
      p, b = questions[i]
      j = i + b + 1
      f[i] = max(f[i + 1], p + (0 if j > n else f[j]))
    return f[0]

class Solution {
  public long mostPoints(int[][] questions) {
    int n = questions.length;
    long[] f = new long[n + 1];
    for (int i = n - 1; i >= 0; --i) {
      int p = questions[i][0], b = questions[i][1];
      int j = i + b + 1;
      f[i] = Math.max(f[i + 1], p + (j > n ? 0 : f[j]));
    }
    return f[0];
  }
}

class Solution {
public:
  long long mostPoints(vector<vector<int>>& questions) {
    int n = questions.size();
    long long f[n + 1];
    memset(f, 0, sizeof(f));
    for (int i = n - 1; ~i; --i) {
      int p = questions[i][0], b = questions[i][1];
      int j = i + b + 1;
      f[i] = max(f[i + 1], p + (j > n ? 0 : f[j]));
    }
    return f[0];
  }
};

func mostPoints(questions [][]int) int64 {
  n := len(questions)
  f := make([]int64, n+1)
  for i := n - 1; i >= 0; i-- {
    p := int64(questions[i][0])
    if j := i + questions[i][1] + 1; j <= n {
      p += f[j]
    }
    f[i] = max(f[i+1], p)
  }
  return f[0]
}

function mostPoints(questions: number[][]): number {
  const n = questions.length;
  const f = Array(n + 1).fill(0);
  for (let i = n - 1; i >= 0; --i) {
    const [p, b] = questions[i];
    const j = i + b + 1;
    f[i] = Math.max(f[i + 1], p + (j > n ? 0 : f[j]));
  }
  return f[0];
}