2140. 解决智力问题

发表于 分类于 阅读次数： Waline： 本文字数： 796 阅读时长 ≈ 3 分钟

考点

  • 线性DP

思路

一、问题概述

给定一个长度为 \(n\) 的题目序列 questions，其中 \[ \text{questions}[i] = (\text{points}_i,\ \text{brainpower}_i) \] 含义如下：

  • 若选择解答第 \(i\) 题（下标从 0 开始），可获得 \(\text{points}_i\) 分；

  • 同时必须跳过接下来的 \(\text{brainpower}_i\) 道题，即下一次可选择的题目下标为 \[ i + \text{brainpower}_i + 1 \]

  • 每道题最多只能选择一次，目标是最大化总得分。

该问题本质上是一个带跳跃约束的序列决策问题，适合使用动态规划建模。

二、问题建模

1. 状态定义

采用 前向动态规划，定义一维数组： \[ f[i] = \text{到达第 } i \text{ 题之前（尚未决定是否做第 } i \text{ 题）时的最大得分} \] 其中：

  • 使用 1-based 下标（即第 \(i\) 题对应 questions[i-1]）；
  • \(f[i]\) 不包含第 \(i\) 题本身的得分，仅表示“走到这里”的历史最优结果。

2. 状态含义说明

在处理第 \(i\) 题时，存在两种决策：

  1. 不做第 \(i\) 题 得分不变，直接进入第 \(i+1\) 题；

  2. 做第 \(i\) 题

    • 得分增加 \(\text{points}_i\)；

    • 跳过接下来的 \(\text{brainpower}_i\) 题，转移到第 \[ i + \text{brainpower}_i + 1 \text{ 题} \]

三、初始条件

  • 尚未处理任何题目时，得分为 0：

\[ f[1] = 0 \]

  • 其余状态初始为 0（表示尚不可达或尚未更新）；
  • 使用变量 res 维护“已做过某道题”情况下的最大得分。

四、状态转移方程

设第 \(i\) 题的参数为： \[ v = \text{points}_i,\quad u = \text{brainpower}_i \]

1. 不做第 \(i\) 题

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

含义：保持当前得分，顺延到下一题。

2. 做第 \(i\) 题

  • 当前得分变为：

\[ f[i] + v \]

  • 跳转目标位置：

\[ j = i + u + 1 \]

  • 若 \(j \le n\)，则：

\[ f[j] = \max(f[j],\ f[i] + v) \]

3. 维护答案

由于“做题”操作可能直接跳出后续区间，最终答案不一定出现在某个固定的 \(f[i]\) 中，因此需要在转移过程中维护全局最优值： \[ \text{res} = \max(\text{res},\ f[i] + v) \]

五、答案定义

最终答案为： \[ \boxed{\text{res}} \] 即在所有“选择某题作为最后一次解题”的方案中，所能获得的最大得分。

六、算法复杂度分析

  • 时间复杂度： \[ O(n) \] 每道题仅进行常数次状态转移。

  • 空间复杂度： \[ O(n) \] 使用一个长度为 \(n\) 的一维 DP 数组。

七、参考实现（含完整注释）

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
class Solution {
public:
    static const int maxn = 1e5 + 5;

    long long mostPoints(vector<vector<int>>& questions) {
        // f[i]: 到达第 i 题之前（尚未决定是否做第 i 题）时的最大得分
        long long f[maxn] = {};

        int n = questions.size();
        long long res = 0; // 全局最优答案

        for (int i = 1; i <= n; ++i) {
            int v = questions[i - 1][0]; // 第 i 题的得分
            int u = questions[i - 1][1]; // 第 i 题的 brainpower

            // 情况一：做第 i 题
            // 当前得分为 f[i] + v
            res = max(res, f[i] + v);

            // 情况二：不做第 i 题，直接进入第 i+1 题
            f[i + 1] = max(f[i + 1], f[i]);

            // 做第 i 题后，跳到第 i + u + 1 题
            if (i + u + 1 <= n) {
                f[i + u + 1] = max(f[i + u + 1], f[i] + v);
            }
        }

        return res;
    }
};