题目描述：
给你一个下标从 0 开始的二维整数数组 questions ，其中 questions[i] = [pointsi, brainpoweri] 。
这个数组表示一场考试里的一系列题目，你需要 按顺序 （也就是从问题 0 开始依次解决），针对每个问题选择 解决 或者 跳过 操作。解决问题 i 将让你 获得 pointsi 的分数，但是你将 无法 解决接下来的 brainpoweri 个问题（即只能跳过接下来的 brainpoweri 个问题）。如果你跳过问题 i ，你可以对下一个问题决定使用哪种操作。
比方说，给你
1
| questions = [[3, 2], [4, 3], [4, 4], [2, 5]]
|
- 如果问题
0 被解决了， 那么你可以获得 3 分，但你不能解决问题 1 和 2 。 - 如果你跳过问题
0 ，且解决问题 1 ，你将获得 4 分但是不能解决问题 2 和 3 。
请你返回这场考试里你能获得的 最高 分数。
数据范围：
$1\le questions.len \le 10^5; 1\le points_i, brainpower_i \le 10^5$
题解：
考虑选与不选，设 $dp[i]$ 表示以 $i$ 结尾的最大分数。
选 $i$ ，则 $dp[i] = dp[k] + points[i], i \ge k + brainpower[k] + 1$
不选 $i$ ，则 $dp[i] = dp[i - 1]$ 。
但是这样的话需要使用双重循环，时间复杂度太高。
而且存在后效性，选 $i$ 的话会对后面的造成影响，考虑如果反向的话， $dp[i]$ 表示从 $i$ 到最后最大分数。
选 $i$ ，则 $dp[i] = dp[i + brainpower[i] + 1] \or points[i]$ 。
不选 $i$ ，则 $dp[i] = dp[i + 1]$ 。
也可以使用记忆化搜索，根本不用费心思考虑。
代码：
递推
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
| auto optimize_cpp_stdio = []()
{
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
return 0;
}();
class Solution
{
public:
const static int maxn = 1e5 + 10;
const static int maxm = 1e5 + 10;
const int INF = 0x3f3f3f3f;
long long mostPoints(vector<vector<int>> &questions)
{
int n = questions.size();
vector<long long> dp(n);
dp[n - 1] = questions[n - 1][0];
for (int i = n - 2; i >= 0; --i)
{
dp[i] = dp[i + 1];
if (i + questions[i][1] + 1 < n)
dp[i] = max(dp[i], 1l * questions[i][0] + dp[i + questions[i][1] + 1]);
else
dp[i] = max(dp[i], 1ll * questions[i][0]);
}
return dp[0];
}
};
|
记忆化搜索
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
| auto optimize_cpp_stdio = []()
{
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
return 0;
}();
class Solution
{
public:
const static int maxn = 1e5 + 10;
const static int maxm = 1e5 + 10;
const int INF = 0x3f3f3f3f;
vector<long long> dp;
long long dfs(int step, int n, vector<vector<int>> &questions)
{
if (step >= n)
return 0;
if (dp[step] != -1)
return dp[step];
long long ret = 0;
return dp[step] = max(dfs(step + 1, n, questions), dfs(step + questions[step][1] + 1, n, questions) + questions[step][0]);
}
long long mostPoints(vector<vector<int>> &questions)
{
int n = questions.size();
dp.resize(n, -1);
dfs(0, n, questions);
return dp[0];
}
};
|