LeetCode 2140. 解决智力问题

2026-09-13 HGNULB 约 3 分钟

文章信息 2 个分类 2 个标签

分类

LeetCode 中等

题目描述

✅ 2140. 解决智力问题

题意分析

题目必须按给定顺序考虑。做第 i 题获得 questions[i][0] 分，但随后 questions[i][1] 道题都不能做；主动跳过当前题则没有额外限制，可以继续决定下一题。

要最大化总分，不能只看当前题分数高低，还要比较它强制跳过后损失的后续机会。之前的选择只决定从哪个位置恢复决策，因此可以按剩余题目的起点保存最优值。

解法：倒序后缀 DP 比较做与不做

核心思路

[!blue]

定义 dp[i] 为从第 i 题开始、当前已经可以自由决定做或跳过时，后缀中能获得的最高分。dp[n] = 0 表示所有题目已经处理完，没有后续得分。

当前只有两种选择。跳过第 i 题，直接得到 dp[i + 1]；做第 i 题，先获得它的分数，再从 i + brainpower[i] + 1 继续，得到“当前分数 + 对应后缀最优值”。跳过数量指当前题之后的题，所以恢复决策的位置必须再加一。

这两种选择覆盖了所有合法方案，而且分支确定后，剩余问题仍是同样的后缀选择问题。因此对两种总收益取最大，就是 dp[i]。两个后继下标都大于 i，从后向前计算时依赖已经准备好。

若做题后的后继达到或越过 n，说明剩余题目全部被跳过，后续收益统一为 0。代码将后继截到 n，直接复用空后缀状态。总分可能超过单个 int 的范围，状态使用 Java long 或 Go int64。

解题步骤

创建长度为 n + 1 的宽整数数组，保留 dp[n] = 0。

从 i = n - 1 倒序遍历到 0。

计算做当前题后第一个可选位置 next = min(n, i + questions[i][1] + 1)。

比较跳过的 dp[i + 1] 和做题的 questions[i][0] + dp[next]，将较大值写入 dp[i]。

返回 dp[0]，即从整场考试起点能取得的最高分。

代码实现

class Solution {
    public long mostPoints(int[][] questions) {
        int n = questions.length;
        long[] dp = new long[n + 1];

        for (int i = n - 1; i >= 0; i--) {
            int next = Math.min(n, i + questions[i][1] + 1);

            dp[i] = Math.max(dp[i + 1], questions[i][0] + dp[next]);
        }

        return dp[0];
    }
}

func mostPoints(questions [][]int) int64 {
    n := len(questions)
    dp := make([]int64, n+1)
    for i := n - 1; i >= 0; i-- {
        next := min(n, i+questions[i][1]+1)
        dp[i] = max(dp[i+1], int64(questions[i][0])+dp[next])
    }
    return dp[0]
}

复杂度分析

时间复杂度：$O(n)$，每个后缀状态只比较两个候选，计算一次。

空间复杂度：$O(n)$，保存全部后缀的最优分数。

分数累加使用 long 或 int64；Go 需要先把当前单题分数转为 int64，再与状态相加。

关键点总结

[!green]

状态表示从哪个位置恢复自由选择，不需要记录此前已做题目的完整序列。

做与不做覆盖当前全部决策，每个分支再接上后续最优值即可。

空后缀的零收益统一处理越界跳转，倒序计算保证后继状态先完成。

易错点总结

[!yellow]

做完当前题后的恢复位置是 i + brainpower[i] + 1，漏掉一会把必须跳过的题重新纳入选择。

高分题可能强制放弃更高的后续收益，不能按当前分数贪心选择。

越过数组末尾时收益应当为零，不能直接访问超出范围的下标。

跳转距离因题而异，可能访问任意更后的状态，不能直接压缩成只保存最近两个值的滚动数组。

相似题目

题目	难度	关联与区别
198. 打家劫舍	中等	同样比较选与不选，但本题跳过长度可变，必须保留任意后继位置的最优值。
1235. 规划兼职工作	困难	同样选择当前收益后跳到下一个兼容位置；兼职工作需要按时间寻找兼容任务。

转载与许可

作者 HGNULB

链接 https://hgnulb.github.io/blog/2026/50138572

许可本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！