力扣 2140. 解决智力问题_力扣2140-CSDN博客

本文链接：https://blog.csdn.net/csdn_muxin/article/details/122554061

本文针对LeetCode上的一道题“脑力解题”，提供了详细的解题思路和动态规划算法实现。通过倒序遍历和动态规划的方法，高效地解决了问题，避免了超时情况。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

题目来源：https://leetcode-cn.com/problems/solving-questions-with-brainpower/

大致题意：
给一个二维数组 questions，其中每个元素，即一维数组为 (得分，跳过题目) 的二元组，表示做了该题会得到的分数，和接下来需要跳过的题目个数

求出最多能得多少分

思路

根据题意，如果想做题目 i，那么 i 之前的题目 j 对应的跳过题目的数量需要小于 i - j
那么对于每个题目 i，都需要遍历之前的所有题目 j，查看是否满足要求，并统计相应的得分，最后对比取得最大值。这样时间复杂度为 O(n²)，会超时

那如果倒着来呢，用 dp[i] 表示从 i 开始到结尾能有的最大得分，那么对于当前的 i ，设其跳过题目数量为 x，那么跳题后能做的题的最小索引为 idx = i + x + 1。在 idx 小于 n 时，代表做完题目 i，还可以做题，于是 dp[i] = max(dp[idx] + 第 i 题的得分, dp[i + 1])

显然这是一个动态规划的过程

动态规划

用 dp[i] 表示从 i 开始到结尾能有的最大得分，n 表示二维数组长度

初始时，dp[n - 1] = 第 n - 1 题的得分
从 n - 2 开始倒序遍历
对于当前的 i，首先取 dp[i] 为做该题的得分和不做该题得分的最大值，即 dp[i] = max(dp[i + 1], 第 i 题的得分)，然后判断做完该题是否还可以做题，若可以，取 dp[i] 为做该题得分 + 之后的得分与不做该题得分的最大值，即 dp[i] = max(dp[idx] + 第 i 题的得分, dp[i + 1])

代码：

public long mostPoints(int[][] questions) {
        int n = questions.length;
        long[] dp = new long[n];
        // 初始状态
        dp[n - 1] = questions[n - 1][0];
        // 倒序遍历
        for (int i = n - 2; i >= 0; i--) {
            // 当前得分的初始值
            dp[i] = Math.max(questions[i][0], dp[i + 1]);
            int idx = questions[i][1] + i + 1;
            if (idx > n) {
                continue;
            }
            // 若做完该题还可以做题
            // 更新当前的分
            dp[i] = Math.max(dp[idx] + questions[i][0], dp[i + 1]);
        }
        return dp[0];
    }