Question

2140. 解决智力问题

English Version

题目描述

给你一个下标从 0 开始的二维整数数组 questions ，其中 questions[i] = [pointsi, brainpoweri] 。

这个数组表示一场考试里的一系列题目，你需要 按顺序 （也就是从问题 0 开始依次解决），针对每个问题选择 解决 或者 跳过 操作。解决问题 i 将让你 获得  pointsi 的分数，但是你将 无法 解决接下来的 brainpoweri 个问题（即只能跳过接下来的 brainpoweri 个问题）。如果你跳过问题 i ，你可以对下一个问题决定使用哪种操作。

• 比方说，给你 questions = [[3, 2], [4, 3], [4, 4], [2, 5]] ：
  • 如果问题 0 被解决了， 那么你可以获得 3 分，但你不能解决问题 1 和 2 。
  • 如果你跳过问题 0 ，且解决问题 1 ，你将获得 4 分但是不能解决问题 2 和 3 。

请你返回这场考试里你能获得的 最高 分数。

 

示例 1：

输入：questions = [[3,2],[4,3],[4,4],[2,5]]
输出：5
解释：解决问题 0 和 3 得到最高分。
- 解决问题 0 ：获得 3 分，但接下来 2 个问题都不能解决。
- 不能解决问题 1 和 2
- 解决问题 3 ：获得 2 分
总得分为：3 + 2 = 5 。没有别的办法获得 5 分或者多于 5 分。

示例 2：

输入：questions = [[1,1],[2,2],[3,3],[4,4],[5,5]]
输出：7
解释：解决问题 1 和 4 得到最高分。
- 跳过问题 0
- 解决问题 1 ：获得 2 分，但接下来 2 个问题都不能解决。
- 不能解决问题 2 和 3
- 解决问题 4 ：获得 5 分
总得分为：2 + 5 = 7 。没有别的办法获得 7 分或者多于 7 分。

 

提示：

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

解法

方法一：记忆化搜索

我们设计一个函数 $dfs(i)$，表示从第 $i$ 个问题开始解决，能够获得的最高分数。那么答案就是 $dfs(0)$。

函数 $dfs(i)$ 的计算方式如下：

• 如果 $i \geq n$，表示已经解决完所有问题，返回 $0$；
• 否则，设第 $i$ 个问题的分数为 $p$，需要跳过的问题数为 $b$，那么 $dfs(i) = \max(p + dfs(i + b + 1), dfs(i + 1))$。

为了避免重复计算，我们可以使用记忆化搜索的方法，用一个数组 $f$ 记录所有已经计算过的 $dfs(i)$ 的值。

时间复杂度 $O(n)$，空间复杂度 $O(n)$。其中 $n$ 是问题的数量。

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);
}

方法二：动态规划

我们定义 $f[i]$ 表示从第 $i$ 个问题开始解决，能够获得的最高分数。那么答案就是 $f[0]$。

考虑 $f[i]$，第 $i$ 个问题的分数为 $p$，需要跳过的问题数为 $b$。如果我们解决了第 $i$ 个问题，那么接下来我们需要解决 $b$ 个问题，因此 $f[i] = p + f[i + b + 1]$。如果我们跳过了第 $i$ 个问题，那么接下来我们从第 $i + 1$ 个问题开始解决，因此 $f[i] = f[i + 1]$。两者取最大值即可。状态转移方程如下：

$$ f[i] = \max(p + f[i + b + 1], f[i + 1]) $$

我们从后往前计算 $f$ 的值，最后返回 $f[0]$ 即可。

时间复杂度 $O(n)$，空间复杂度 $O(n)$。其中 $n$ 是问题的数量。

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];
}