# [2140. 解决智力问题](https://leetcode.cn/problems/solving-questions-with-brainpower)
[English Version](/solution/2100-2199/2140.Solving%20Questions%20With%20Brainpower/README_EN.md)
## 题目描述
<!-- 这里写题目描述 -->
<p>给你一个下标从 <strong>0</strong> 开始的二维整数数组 <code>questions</code> ，其中 <code>questions[i] = [points<sub>i</sub>, brainpower<sub>i</sub>]</code> 。</p>
<p>这个数组表示一场考试里的一系列题目，你需要 <strong>按顺序</strong> （也就是从问题 <code>0</code><strong> </strong>开始依次解决），针对每个问题选择 <strong>解决</strong> 或者 <strong>跳过</strong> 操作。解决问题 <code>i</code> 将让你 <b>获得</b> <code>points<sub>i</sub></code> 的分数，但是你将 <strong>无法</strong> 解决接下来的 <code>brainpower<sub>i</sub></code> 个问题（即只能跳过接下来的 <code>brainpower<sub>i</sub></code><sub> </sub>个问题）。如果你跳过问题 <code>i</code> ，你可以对下一个问题决定使用哪种操作。</p>
<ul>
<li>比方说，给你 <code>questions = [[3, 2], [4, 3], [4, 4], [2, 5]]</code> ：
<ul>
<li>如果问题 <code>0</code> 被解决了， 那么你可以获得 <code>3</code> 分，但你不能解决问题 <code>1</code> 和 <code>2</code> 。</li>
<li>如果你跳过问题 <code>0</code> ，且解决问题 <code>1</code> ，你将获得 <code>4</code> 分但是不能解决问题 <code>2</code> 和 <code>3</code> 。</li>
</ul>
</li>
</ul>
<p>请你返回这场考试里你能获得的 <strong>最高</strong> 分数。</p>
<p> </p>
<p><strong>示例 1：</strong></p>
<pre><b>输入：</b>questions = [[3,2],[4,3],[4,4],[2,5]]
<b>输出：</b>5
<b>解释：</b>解决问题 0 和 3 得到最高分。
- 解决问题 0 ：获得 3 分，但接下来 2 个问题都不能解决。
- 不能解决问题 1 和 2
- 解决问题 3 ：获得 2 分
总得分为：3 + 2 = 5 。没有别的办法获得 5 分或者多于 5 分。
</pre>
<p><strong>示例 2：</strong></p>
<pre><b>输入：</b>questions = [[1,1],[2,2],[3,3],[4,4],[5,5]]
<b>输出：</b>7
<b>解释：</b>解决问题 1 和 4 得到最高分。
- 跳过问题 0
- 解决问题 1 ：获得 2 分，但接下来 2 个问题都不能解决。
- 不能解决问题 2 和 3
- 解决问题 4 ：获得 5 分
总得分为：2 + 5 = 7 。没有别的办法获得 7 分或者多于 7 分。
</pre>
<p> </p>
<p><strong>提示：</strong></p>
<ul>
<li><code>1 <= questions.length <= 10<sup>5</sup></code></li>
<li><code>questions[i].length == 2</code></li>
<li><code>1 <= points<sub>i</sub>, brainpower<sub>i</sub> <= 10<sup>5</sup></code></li>
</ul>
## 解法
<!-- 这里可写通用的实现逻辑 -->
**方法一：记忆化搜索**
我们设计一个函数 $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$ 是问题的数量。
**方法二：动态规划**
我们定义 $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$ 是问题的数量。
<!-- tabs:start -->
### **Python3**
<!-- 这里可写当前语言的特殊实现逻辑 -->
```python
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)
```
```python
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]
```
### **Java**
<!-- 这里可写当前语言的特殊实现逻辑 -->
```java
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));
}
}
```
```java
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];
}
}
```
### **C++**
```cpp
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);
}
};
```
```cpp
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];
}
};
```
### **Go**
```go
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)
}
func max(a, b int64) int64 {
if a > b {
return a
}
return b
}
```
```go
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]
}
func max(a, b int64) int64 {
if a > b {
return a
}
return b
}
```
### **TypeScript**
```ts
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);
}
```
```ts
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];
}
```
### **...**
```
```
<!-- tabs:end -->